Java-LeetCode124. 二叉树的最大路径和-层序遍历

• 算法
  • 层序遍历
  • 1.使用队列层序遍历二叉树
  • 2.维护一个max，从最底层开始计算最大路径和
  • 3.当节点是叶子节点时，节点值和max比较取最大值
  • 4.当节点不是叶子节点时，有这么几种可能的路径和:
    • 4.1 当前节点值
    • 4.2 MAX(左子节点值, 右子节点值) + 当前节点值
    • 4.3 左子节点值 + 右子节点值 + 当前节点值
    • 取三者最大，同时当前节点值要更新为MAX(4.1, 4.2)，继续上一层的计算

public int maxPathSum(TreeNode root) {
    if (root == null) {
        return 0;
    }

    ArrayList<TreeNode> list = new ArrayList<>(10);
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode curr = queue.poll();
        list.add(curr);
        if (curr.left != null) {
            queue.offer(curr.left);
        }
        if (curr.right != null) {
            queue.offer(curr.right);
        }
    }
    int max = Integer.MIN_VALUE;
    for (int i = list.size() - 1; i >= 0; i--) {
        TreeNode curr = list.get(i);
        if (curr.left == null && curr.right == null) {
            max = Math.max(max, curr.val);
        } else  {
            int left = curr.left == null ? 0 : curr.left.val;
            int right = curr.right == null ? 0 : curr.right.val;
            int rootValue = curr.val;
            curr.val = Math.max(rootValue, Math.max(left, right) + rootValue);
            max = Math.max(max, Math.max(curr.val, left + right + rootValue));
        }
    }
    return max;
}