需要记录Path
一般来说需要用DFS，则需要考虑回溯
Path Sum II
- 注意Binary Tree上的回溯是在完成当前这个递归的时候，即加入results和call left and right之后
- 另外由于要求root-to-leaf，所以必须要进行root.left和root.right的check
- O(n), space O(H) (worst case)
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> results = new ArrayList<>();
if (root == null) return results;
dfs(root, sum, new ArrayList<>(), results);
return results;
}
private void dfs(TreeNode root, int sum, List<Integer> path, List<List<Integer>> results) {
if (root == null) return;
sum -= root.val;
path.add(root.val);
if (root.left == null && root.right == null) {
if (sum == 0) {
results.add(new ArrayList<>(path));
path.remove(path.size()-1);
return;
}
}
dfs(root.left, sum, path, results);
dfs(root.right, sum, path, results);
path.remove(path.size()-1);
}
}
Path Sum III
通过分析递归的特点，每一个pathSum包括以当前node为起点的path，还有左子树的path sum 以及右子树的path sum。很容易想到recursive 的办法，注意在这里用了两次DFS/recursive，遍历了每个点，并且对于每个点，都从这个点出发，找到了他的pathSum
Space: O(n) due to recursion.
Time: O(n^2) in worst case (no branching); O(nlogn) in best case (balanced tree).
public class Solution {
public int pathSum(TreeNode root, int sum) {
if (root == null) return 0;
return pathSumFrom(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}
//从node出发，有多少个paths能达到sum
private int pathSumFrom(TreeNode node, int sum) {
if (node == null) return 0;
return (node.val == sum ? 1 : 0)
+ pathSumFrom(node.left, sum - node.val) + pathSumFrom(node.right, sum - node.val);
}
}
Sum Root to Leaf Numbers
- dfs可破，这道题唯一需要注意的是，因为传递的path是int，不是一个Obj而是primitive type，所以每次传递的就是当前递归栈里的值，不需要回溯
Binary Tree Maximum Path Sum
D&C
- Naive：左右子树的MPS，以及root
- 左右子树的MPS，并不能保证与root是相连的，所以以上方案不行，Path是需要纳入考虑的.**当计算这类D&C问题的时候，如果要分成left, root, and right一定要考虑清楚，root是否相连/要取到
- 整个树的MPS = Max（对于每个点，包含这个点的MPS），这样的MPS有许多计算过了的值，而我们只关心最大的，所以只需要用一个global max来存这个值
- tricky part: 这里其实有两种路径，一种是从root开始往下走到某个点的MPS，还有一种是跨过root点的MPS。注意到helper function是用来计算第一种MPS的，而第二种MPS则是用来确定global max的.
- 而这题的tricky之处就在于，在helper的计算过程中，是可以同时更新MPS的（在这个更新到过程中，只需要跟left + right + root比较，因为如果跨过不是更优解的话，就会在之前被0给过滤了）。因为在计算从root往下走的过程需要计算左右子树的子问题，这时候就可以跟0的比较进行取舍
- Naive：左右子树的MPS，以及root
总结和思考：一个重要的问题是，我们只能从 root 开始，也没有 parent 指针，但是最优的路径可能却和 root 是不连续的，这就切断了 Binary Tree divide & conquer / Tree DFS 里面大多数做法中非常依赖的性质，即层层递归之前 左/右 子树和根节点的联系。然而套路还是要用的，要么这题就没法做了。。好在问题没有要求返回具体 path ，只要一个 max sum, 想连接全局最优就要用一个全局变量 int max. 从 leaf node 开始 bottom-up 进行处理的时候还不需要考虑“切断”的问题，因此还可以用套路，注意随时更新全局 max 就好。从 bottom-up 的角度看，这是一个从底部不停 merge 最优的子路径在根节点会和的过程。
public class Solution {
int maxVal;
public int maxPathSum(TreeNode root) {
maxVal = Integer.MIN_VALUE;
helper(root);
return maxVal;
}
//从root开始往下走的到某个点的最大路径sum，通过这个过程的计算，可以不断的更新全局最优解
public int helper(TreeNode root) {
if (root == null) return 0;
//当某一边为负数的时候，直接抛弃（取0）
int left = Math.max(0, helper(root.left));
int right = Math.max(0, helper(root.right));
maxVal = Math.max(maxVal, left + right + root.val);
return Math.max(left, right) + root.val;
}
}
另一种办法是引入ResultType
public class Solution {
/**
* @param root: The root of binary tree.
* @return: An integer.
*/
private class ResultType {
// singlePath: 从root往下走到任意点的最大路径，至少包含一个点
// maxPath: 从树中任意到任意点的最大路径，这条路径至少包含一个点
int singlePath, maxPath;
ResultType(int singlePath, int maxPath) {
this.singlePath = singlePath;
this.maxPath = maxPath;
}
}
private ResultType helper(TreeNode root) {
if (root == null) {
return new ResultType(Integer.MIN_VALUE, Integer.MIN_VALUE);
}
// Divide
ResultType left = helper(root.left);
ResultType right = helper(root.right);
// Conquer
int singlePath =
Math.max(0, Math.max(left.singlePath, right.singlePath)) + root.val;
int maxPath = Math.max(left.maxPath, right.maxPath);
maxPath = Math.max(maxPath,
Math.max(left.singlePath, 0) +
Math.max(right.singlePath, 0) + root.val);
return new ResultType(singlePath, maxPath);
}
public int maxPathSum(TreeNode root) {
ResultType result = helper(root);
return result.maxPath;
}
}