Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
1 / 2 3 5 All root-to-leaf paths are:
["1->2->5", "1->3"]
用 StringBuilder 传递可以省去递归中新建的 string copies.
StringBuilder 的回溯也很简单，直接 setLength(int len) 就行。
在 leaf node 上以 sb.setLength() 收尾是为了 backtracking，因为后面的两个 dfs 都没有做，不走到底是不会回溯的，要由到了 leaf node 那一层递归进行处理。这点和常见的 subsets 和 permutations 不太一样，那两题中收尾直接 add 然后 return 就可以了，而回溯在 dfs 之后做。
在 dfs 之后直接 backtracking 会遇到问题，例如路径上某个分叉上只有一边有节点，向 null 方向探索之后会删掉来路。
Copy public class Solution {
public void help(List<String> list, TreeNode node, StringBuilder sb) {
if (node == null) return;
// 存盘，保存当前路径
int len=sb.length();
sb.append(node.val);
if (node.left == null && node.right == null) {
list.add(sb.toString());
// 抹掉末尾数字
sb.setLength(len);
return;
}
sb.append("->");
help(list, node.left, sb);
help(list, node.right, sb);
// 抹掉箭头和前一个数字
sb.setLength(len);
}
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<String>();
help(res, root, new StringBuilder());
return res;
}
} 和前一题研究的 Tree DFS + Backtracking 完全一个套路。只不过回溯的时候，记得把 curSum 也给回溯了就行。
Copy /**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> rst = new ArrayList<List<Integer>>();
if(root == null) return rst;
dfs(rst, root, new ArrayList<Integer>(), 0, sum);
return rst;
}
private void dfs(List<List<Integer>> rst, TreeNode root, List<Integer> list, int curSum, int targetSum){
if(root == null) return;
list.add(root.val);
curSum += root.val;
if(root.left == null && root.right == null){
if(curSum == targetSum){
rst.add(new ArrayList<Integer>(list));
list.remove(list.size() - 1);
return;
}
}
dfs(rst, root.left, list, curSum, targetSum);
dfs(rst, root.right, list, curSum, targetSum);
curSum -= root.val;
list.remove(list.size() - 1);
}
}
Copy public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> rst = new ArrayList<List<Integer>>();
dfs(rst, new ArrayList<Integer>(), root, sum);
return rst;
}
private void dfs(List<List<Integer>> rst, List<Integer> list, TreeNode root, int sum){
if(root == null) return;
if(root.left == null && root.right == null){
if(root.val == sum){
list.add(root.val);
rst.add(new ArrayList<Integer>(list));
list.remove(list.size() - 1);
return;
} else {
return;
}
}
list.add(root.val);
dfs(rst, list, root.left, sum - root.val);
dfs(rst, list, root.right, sum - root.val);
list.remove(list.size() - 1);
}
} 简化版，这次不用存所有的 Paths 了，套用 Tree DFS 模板可以，不过在只求 boolean / int 的情况下，也有更简单直接的写法。
Copy public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
return dfs(root, 0, sum);
}
private boolean dfs(TreeNode root, int curSum, int targetSum){
if(root == null) return false;
curSum += root.val;
if(root.left == null && root.right == null){
if(curSum == targetSum) return true;
}
boolean left = dfs(root.left, curSum, targetSum);
boolean right = dfs(root.right, curSum, targetSum);
curSum -= root.val;
return (left || right);
}
} 或者更直接点，
Copy public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if(root == null) return false;
if(root.left == null && root.right == null && root.val == sum) return true;
return (hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val));
}
} 这题有点 Tricky，不好做。假定有如下的Tree:
Copy 5
/ \
1 -1
/ \ / \
0 -2 3 2 最大和路径有这么几种可能：
从 root 出发，路上看到负数，负数后面存在总和超过负数节点的路径；
最大和在某个从 leaf node 往上走的一条路径上，不过 root.
换句话说，一个重要的问题是，我们只能从 root 开始，也没有 parent 指针，但是最优的路径可能却和 root 是不连续的，这就切断了 Binary Tree divide & conquer / Tree DFS 里面大多数做法中非常依赖的性质，即层层递归之前 左/右 子树和根节点的联系。
然而套路还是要用的，要么这题就没法做了。。好在问题没有要求返回具体 path ，只要一个 max sum, 想连接全局最优就要用一个全局变量 int max. 从 leaf node 开始 bottom-up 进行处理的时候还不需要考虑“切断”的问题，因此还可以用套路，注意随时更新全局 max 就好。从 bottom-up 的角度看，这是一个从底部不停 merge 最优的子路径在根节点会和的过程。
每一层的“三角形”路径都要和全局最优 update 一下，然而不是有效的 path. 最终 return 的结果只是“必须包括当前节点” 的最大 path，由此完成连续的递归结构（recurrence substructure）
另外一个小技巧是，在求 max sum 的情况下，每一个节点可以有 “选”（root.val） 或者 “不选” （0） 两种选择，在单个
Copy 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;
}
} 如果不喜欢这种用全局变量的方式，也可以用如下九章的解法，其实骨子里面的思路一样，把全局变量用一个 tuple 包起来了。
比较值得参考的是这种 dfs 之间传 tuple 的方式很好的解决了信息传递的问题，其中的变量可以是符合递归连续结构的，也可以是全局的，看起来比较适合 generalize 到其他 Tree 的问题。
Copy 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 的递归回溯。
Copy 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;
}
} 如果 dfs 里面共享的变量是 String 或者 primitive type ，那么不存在多层递归共同 reference 的问题，backtracking 的步骤也就可以省去了。
从这个角度看，其实很多看起来非常简洁的 Binary Tree 问题都是因为 dfs 函数里面没有 by reference 的东西，属于 dfs + backtracking 的低配简化版。
Copy 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 解决。 其他部分无压力套模板。
不爱用全局变量也好办，建个长度为 1 的 int[] 当参数传就行了。
Copy public int longestConsecutive(TreeNode root) {
int[] max = new int[1];
dfs(root, null, 0, max);
return max[0];
}
private void dfs(TreeNode root, TreeNode parent, int length, int[] max){
// Not valid path to leaf node
if(root == null) return;
// ADD
if(parent == null || root.val - parent.val == 1){
length ++;
} else {
length = 1;
}
max[0] = Math.max(max[0], length);
dfs(root.left, root, length, max);
dfs(root.right, root, length, max);
}