Leetcode(124) Binary Tree Maximum Path Sum

发表于 | 分类于

Description

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

1
2
3
4
5
6
7
Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

1
2
3
4
5
6
7
8
9
Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

解法

嗯，递归解题，但是坑挺多，首先要注意路径不一定从根经过，另外路径必须能够展开成一条直线，这就意味着对于最终路径上的非跟节点必须选择左右子树的一边进行计算，导致递归的返回和进入优先队列的计算值不一样

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    Queue<Integer> q = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });

    public int maxPathSum(TreeNode root) {
        maxPathSumHelper(root);
        return q.element();
    }

    public int maxPathSumHelper(TreeNode root) {
        if (root.left == null && root.right == null) {
            q.offer(root.val);
            return root.val;
        }
        if (root.right == null) {
            int leftMax = maxPathSumHelper(root.left);
            q.offer(leftMax > 0 ? root.val + leftMax : root.val);
            return leftMax > 0 ? root.val + leftMax : root.val;
        }
        if (root.left == null) {
            int rightMax = maxPathSumHelper(root.right);
            q.offer(rightMax > 0 ? root.val + rightMax : root.val);
            return rightMax > 0 ? root.val + rightMax : root.val;
        }
        int leftMax = maxPathSumHelper(root.left);
        int rightMax = maxPathSumHelper(root.right);
        int valA = root.val;
        int valB = leftMax + root.val;
        int valC = rightMax + root.val;
        int valD = leftMax + root.val + rightMax;
        int tmpA = Math.max(valA, valB);
        int tmpB = Math.max(valC, valD);
        q.offer(Math.max(tmpA, tmpB));
        return Math.max(tmpA, valC);
    }
}