力扣小记 117、124、116

117.填充每一个节点的右侧指针Ⅱ

https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii

思路:
用BFS去遍历这颗二叉树, 层序遍历框架用while控制层数, for控制层级节点

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            Node prev = null;
            for (int i = 0; i < size; i++) {
                Node cur = queue.poll();
                if (prev != null) {
                    prev.next = cur;
                }
                prev = cur;
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }
        return root;
    }
}

124.二叉树中的最大路径和

https://leetcode.cn/problems/binary-tree-maximum-path-sum

思路:
明确每个节点需要干什么, 一个节点需要知道自己的val加上当前记录的val会比谁大, 这里用后序遍历拿到每个节点的值, 比较左右子树最大的值求得最后结果

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

func maxPathSum(root *TreeNode) int {
    if root == nil {
        return 0
    }
    var res = 0
    var maxSum func(*TreeNode) int
    maxSum = func(root *TreeNode) int {
        if root == nil {
            return 0
        }
        leftSum := max(0, maxSum(root.Left))
        rightSum := max(0, maxSum(root.Right))
        current := root.Val + leftSum + rightSum
        res = max(res, current)
        return max(leftSum, rightSum) + root.Val
    }
    maxSum(root)
    return res
}

func max(i, j int) int {
    if i > j {
        return i
    }
    return j
}

116.填充每个节点的下一右侧节点的指针

https://leetcode.cn/problems/populating-next-right-pointers-in-each-node

思路:
这道题比117难一点点，因为需要跨越两颗子树连接，可以把二叉树的相邻节点抽象成一个三叉树节点，这样二叉树就变成了一棵三叉树，然后你去遍历这棵三叉树，把每个三叉树节点中的两个节点连接

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */

func connect(root *Node) *Node {
    if root == nil {
        return nil
    }
	traverse(root.Left, root.Right)
    return root
}

func traverse(n1, n2 *Node) {
    if n1 == nil || n2 == nil {
        return
    }
    n1.Next = n2
    traverse(n1.Left, n1.Right)
    traverse(n2.Left, n2.Right)
    traverse(n1.Right, n2.Left)
}