124. Binary Tree Maximum Path Sum (Hard) Microsoft Baidu 高频，和543搭配
Given a 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.
For example:
Given the below binary tree,
1
/ \
2 3
Return6.
Solution 1: DFS O(n); O(h)
Use a global variable to record the max path sum.
For each node there can be four ways that the max path goes through the node:
- Node only
- Max path through Left Child + Node
- Max path through Right Child + Node
- Max path through Left Child + Node + Max path through Right Child
The idea is to keep trace of four paths and pick up the max one in the end. An important thing to note is, root of every subtree need to return maximum path sum such that at most one child of root is involved. This is needed for parent function call. In below code, the value is returned by the recursive function.
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxPathSubtree(root);
return max;
}
private int maxPathSubtree(TreeNode node) {
if (node == null) {
return 0;
}
int left = Math.max(0, maxPathSubtree(node.left));
int right = Math.max(0, maxPathSubtree(node.right));
max = Math.max(max, left + right + node.val);
return Math.max(left, right) + node.val;
}
Follow Up:
1.path sum改成了path长度
变简单了
2.返回path不是sum
变难了，不过思路和原题解法差不多，DFS找的是当前节点到叶节点的和最大的路径，res更新全局最大路径。
List<Integer> path = new ArrayList<>();
int sum = Integer.MIN_VALUE;
public List<Integer> maxPathSum2(TreeNode root) { //将原来的写的代码进行优化
maxPathSubtree(root);
return path;
}
private List<Integer> maxPathSubtree(TreeNode node) {
if (node == null) {
return new ArrayList<>();
}
List<Integer> left = maxPathSubtree(node.left);
List<Integer> right = maxPathSubtree(node.right);
int leftSum = sum(left);
int rightSum = sum(right);
int curSum = node.val + leftSum + rightSum;
if (curSum > sum) {
sum = curSum;
List<Integer> temp = new ArrayList<>(left); //deep copy
temp.add(node.val);
temp.addAll(right);
path = temp;
}
if (leftSum > rightSum) {
left.add(node.val);
return left;
} else {
right.add(node.val);
return right;
}
}
private int sum(List<Integer> list) {
int sum = 0;
for (int num : list) {
sum += num;
}
return sum;
}
List<Integer> res = new ArrayList<>();
public List<Integer> maxPathSum(TreeNode root) {
maxPathSubtree(root);
return res;
}
private List<Integer> maxPathSubtree(TreeNode node) {
if (node == null) {
return new ArrayList<>();
}
List<Integer> left = new ArrayList<>();
List<Integer> right = new ArrayList<>();
if (sum(maxPathSubtree(node.left)) > 0) {
left = maxPathSubtree(node.left);
}
if (sum(maxPathSubtree(node.right)) > 0) {
right = maxPathSubtree(node.right);
}
if (sum(res) < (sum(left) + sum(right) + node.val)) {
List<Integer> temp = new ArrayList<>(left); //deep copy
temp.add(node.val);
for (int num : right) {
temp .add(num);
}
res = temp;
}
if (sum(left) > sum(right)) {
left.add(node.val);
return left;
} else {
right.add(node.val);
return right;
}
}
private int sum(List<Integer> list) {
int sum = 0;
for (int num : list) {
sum += num;
}
return sum;
}
public static void main(String[] args) {
TreeNode root1 = new TreeNode(1);
root1.left = new TreeNode(2);
root1.right = new TreeNode(3);
root1.left.left = new TreeNode(5);
root1.left.right = new TreeNode(13);
root1.left.right.left = new TreeNode(5);
root1.right.left = new TreeNode(2);
root1.right.left.right = new TreeNode(7);
root1.right.right = new TreeNode(-5);
TreeNode root2 = new TreeNode(1);
root2.left = new TreeNode(2);
root2.right = new TreeNode(3);
root2.left.left = new TreeNode(4);
root2.left.right = new TreeNode(5);
BinaryTreeMaximumPathSum test = new BinaryTreeMaximumPathSum();
System.out.println(test.maxPathSum(root1));
}
3.给一个二叉树， 找出从一个叶节点到另一个叶节点最长的路径，返回路径的长度
4.第一题binary tree，找从leaf到leaf的longest path。第二题 找largest path sum， 不一定是leaf到leaf。
5.找二叉树最长路径，针对第二题，followup问了好多递归相关