算法刷题笔记 (29) 二叉树最大宽度 两数相加II 二叉树展开为链表

二叉树最大宽度

二叉树最大宽度

解题思路

层序遍历，在队列中同时记录每一个节点的位置信息，position值：

• 如果左子树入队，那么左子树的位置信息为2 * position
• 如果右子树入队，那么右子树的位置信息为2 * position + 1

解题代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

// 队列节点
type queueNode struct {
    tree *TreeNode  // 树的节点
    position int    // 位置信息
}

func widthOfBinaryTree(root *TreeNode) int {
    if root == nil {
        // 空树的宽度为0
        return 0
    }
    queue := []queueNode{
        queueNode{
            tree: root,
            position: 1,
        },
    }    // 队列，根节点入队
    maxWidth := 1                   // 记录最大宽度
    var last, nextLast *TreeNode    // 遍历层的最后一个节点，下一层的最后一个节点
    last = root
    // 对树进行层序遍历
    for len(queue) > 0 {
        // 队头节点出队
        cur := queue[0]
        queue = queue[1:]
        // 访问队头节点
        if cur.tree.Left != nil {
            // 左子树不为空，入队
            queue = append(queue, queueNode{ tree: cur.tree.Left, position: 2*cur.position})
            nextLast = cur.tree.Left
        }
        if cur.tree.Right != nil {
            // 右子树不为空，入队
            queue = append(queue, queueNode{ tree: cur.tree.Right, position: 2*cur.position+1})
            nextLast = cur.tree.Right
        }
        if cur.tree == last {
            // 本节点是本层最后一个节点
            // 队列中记录了下一层的所有节点，计算宽度
            if len(queue) > 0 && queue[len(queue)-1].position-queue[0].position+1 > maxWidth {
                maxWidth = queue[len(queue)-1].position-queue[0].position+1
            }
            // 更新最后一个节点
            last = nextLast
        }
    }
    return maxWidth
}

两数相加 II

两数相加 II

解题思路

可以用两个栈记录两个链表中存储的数字：

• 遍历两个链表，将两个链表中的数字记录在栈中
• 依次弹出栈中数字相加，构建结果链表

解题代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    stack1 := make([]int, 0)    // 记录l1中数字的栈
    stack2 := make([]int, 0)    // 记录l2中数字的栈
    top1, top2 := -1, -1        // 两个栈的栈顶指针
    // 遍历两个链表，将两个链表中的数字记录在栈中
    p, q := l1, l2              // p, q分别为l1, l2的遍历指针
    for p != nil || q != nil {
        if p != nil {
            stack1 = append(stack1, p.Val)
            top1++
            p = p.Next
        }
        if q != nil {
            stack2 = append(stack2, q.Val)
            top2++
            q = q.Next
        }
    }
    // 弹出栈中数字相加
    newList := &ListNode{}  // 存储结果的链表的虚拟链表头
    var c int               // 进位
    for top1 >= 0 || top2 >= 0 || c > 0{
        var n1, n2 int  // 本位的两个数字
        if top1 >= 0 {
            n1 = stack1[top1]
            top1--
        }
        if top2 >= 0 {
            n2 = stack2[top2]
            top2--
        }
        sum := n1+n2+c  // 本位和
        // 采用头插法
        newList.Next = &ListNode{ Val: sum%10, Next: newList.Next}
        // 更新进位
        c = sum/10
    }

    return newList.Next
}

二叉树展开为链表

二叉树展开为链表

解题思路

基于二叉树先序遍历的递归算法，在访问节点时，先记录节点的左右子树以便进行后续的遍历操作，然后将该节点转化为链表节点插入到链表的尾部。

解题代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode)  {
    newHead := &TreeNode{}      // 虚拟头节点
    rear := newHead             // 指向链表的最后一个节点
    var preorder func(root *TreeNode)
    preorder = func(root *TreeNode) {   // 二叉树的先序遍历
        if root != nil {
            // 访问节点
            // 记录左右子树
            left := root.Left
            right := root.Right
            // 变化为链表节点
            root.Left = nil
            root.Right = nil
            // 插入到rear之后
            rear.Right = root
            rear = rear.Right

            // 递归遍历左右子树
            preorder(left)
            preorder(right)
        }
    }

    preorder(root)
}

Excel表列名称

Excel表列名称

解题思路

从1开始的26进制转换，在进行进制转换之前，需要对columnNumber执行减一操作，从而实现整体的偏移。

解题代码

func convertToTitle(columnNumber int) string {
    var res string          // 返回的字符串
    for columnNumber > 0 {
        columnNumber--
        res = string(columnNumber%26+'A') + res
        columnNumber = columnNumber/26
    }

    return res
}