另外一个小技巧是，在求 max sum 的情况下，每一个节点可以有 “选”（root.val） 或者 “不选” （0） 两种选择，在单个
public class Solution {
// 全局变量，用于连接不连续的状态
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfsBottomUp(root);
return max;
}
private int dfsBottomUp(TreeNode root){
if(root == null) return 0;
// 检查两边的做大路径和，或者直接抛弃（取值为0）
// 因此当一个小三角形一边为负数的时候
// 最后返回的结果看起来是三个点的和，其实只是一条边
int left = Math.max(0, dfsBottomUp(root.left));
int right = Math.max(0, dfsBottomUp(root.right));
// 检查通过当前 “root” 的三角形路线（拐弯）
// 不需要单独再取 Left / Right 中的最大值
// 因为在 Bottom-Up 的递归中左右子树的最大路径已经被更新过了
// 即其中某个分支为负时，最大子树和 = 最大路径和
max = Math.max(max, left + right + root.val);
// 传递到上一层的路线必须连续且不能拐弯，保持连续的递归状态
return Math.max(left, right) + root.val;
}
}
比较值得参考的是这种 dfs 之间传 tuple 的方式很好的解决了信息传递的问题，其中的变量可以是符合递归连续结构的，也可以是全局的，看起来比较适合 generalize 到其他 Tree 的问题。
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;
}
}
都是套路啊，套路。Top-Bottom 的递归回溯。
public class Solution {
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
// 把当前考虑的节点作为参数的 dfs 结构
private int dfs(TreeNode root, int num){
// 只在叶节点上做计算，这里说明不是有效 path
if(root == null) return 0;
-------------ADD----------------
num += root.val;
------------Leaf Node-----------
if(root.left == null && root.right == null){
return num;
}
------------DFS------------------
int left = dfs(root.left, num * 10);
int right = dfs(root.right, num * 10);
--------Backtracking------------
num -= root.val;
return left + right;
}
}
从这个角度看，其实很多看起来非常简洁的 Binary Tree 问题都是因为 dfs 函数里面没有 by reference 的东西，属于 dfs + backtracking 的低配简化版。
public class Solution {
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
private int dfs(TreeNode root, int num){
if(root == null) return 0;
if(root.left == null && root.right == null){
return num + root.val;
}
int left = dfs(root.left, (num + root.val) * 10);
int right = dfs(root.right, (num + root.val) * 10);
return left + right;
}
}
全局最优解不一定和 root 与 dfs 递归连续，因而用全局变量 int max 解决。 其他部分无压力套模板。