# 路径与路径和 ## [Binary Tree Paths](https://leetcode.com/problems/binary-tree-paths/) 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 方向探索之后会删掉来路。 ```java public class Solution { public void help(List 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 binaryTreePaths(TreeNode root) { List res = new ArrayList(); help(res, root, new StringBuilder()); return res; } } ``` ## [113. Path Sum II](https://leetcode.com/problems/path-sum-ii/) 和前一题研究的 Tree DFS + Backtracking 完全一个套路。只不过回溯的时候，记得把 curSum 也给回溯了就行。 ```java /** * 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> pathSum(TreeNode root, int sum) { List> rst = new ArrayList>(); if(root == null) return rst; dfs(rst, root, new ArrayList(), 0, sum); return rst; } private void dfs(List> rst, TreeNode root, List 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(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); } } ``` * 5/27 号重做了一遍，这次的代码 ```java public class Solution { public List> pathSum(TreeNode root, int sum) { List> rst = new ArrayList>(); dfs(rst, new ArrayList(), root, sum); return rst; } private void dfs(List> rst, List 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(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); } } ``` ## [112. Path Sum I](https://leetcode.com/problems/path-sum/) 简化版，这次不用存所有的 Paths 了，套用 Tree DFS 模板可以，不过在只求 boolean / int 的情况下，也有更简单直接的写法。 ```java 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); } } ``` 或者更直接点， ```java 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)); } } ``` ## [ Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum/) 这题有点 Tricky，不好做。假定有如下的Tree: ``` 5 / \ 1 -1 / \ / \ 0 -2 3 2 ``` 最大和路径有这么几种可能： * 从 root 出发，路上看到负数，不采用； * 从 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） 两种选择，在单个 ```java 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 的问题。 ```java 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; } } ``` ## [Sum Root to Leaf Numbers](https://leetcode.com/problems/sum-root-to-leaf-numbers/) 都是套路啊，套路。Top-Bottom 的递归回溯。 ```java 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 的低配简化版。 ```java 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; } } ``` ## [Binary Tree Longest Consecutive Sequence](https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/) 全局最优解不一定和 root 与 dfs 递归连续，因而用全局变量 int max 解决。 其他部分无压力套模板。 ### 不爱用全局变量也好办，建个长度为 1 的 int\[] 当参数传就行了。 ```java 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); } ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://mnunknown.gitbook.io/algorithm-notes/binary_tree/lu_jing_yu_lu_jing_he.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.