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 方向探索之后会删掉来路。
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;
}
}
public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> ans = new ArrayList<String>();
if(root!=null) search(root, "", ans);
return ans;
}
public void search(TreeNode root, String path, List<String> ans){
if(root.left==null && root.right==null){
ans.add(path+root.val); return;
}
if(root.left!=null) search(root.left, path+root.val+"->", ans);
if(root.right!=null) search(root.right, path+root.val+"->", ans);
}
}
113. Path Sum II
和前一题研究的 Tree DFS + Backtracking 完全一个套路。只不过回溯的时候，记得把 curSum 也给回溯了就行。
/**
* 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);
}
}
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） 两种选择，在单个
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 的问题。
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
都是套路啊，套路。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;
}
}
如果 dfs 里面共享的变量是 String 或者 primitive type ，那么不存在多层递归共同 reference 的问题，backtracking 的步骤也就可以省去了。
从这个角度看，其实很多看起来非常简洁的 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;
}
}
Binary Tree Longest Consecutive Sequence
全局最优解不一定和 root 与 dfs 递归连续，因而用全局变量 int max 解决。 其他部分无压力套模板。
不爱用全局变量也好办，建个长度为 1 的 int[] 当参数传就行了。
就两种方式, 要么是top down, 要么是bottom up
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);
}
Binary Tree Longest Consecutive Sequence II
一次AC, 组织好逻辑后再写代码很清晰.
Postorder DFS搜索, 左边回来递增递减两种可能, 右边也是, 一共四种路径. 包含当前root的两种路径, 左递增加右递减, 左递减加右递增, 更新max.
public class Solution {
int max = 0;
class Entity{
int decLen;
int incLen;
public Entity(int incLen, int decLen){
this.decLen = decLen;
this.incLen = incLen;
}
}
public int longestConsecutive(TreeNode root) {
dfs(root);
return max;
}
public Entity dfs(TreeNode root){
if(root==null){
return new Entity(0,0);
}
Entity left = dfs(root.left);
Entity right = dfs(root.right);
int incLeft = (root.left==null||root.val==root.left.val+1)?left.incLen+1:1;
int incRight = (root.right==null || root.val==root.right.val+1) ? right.incLen+1:1;
int decLeft = (root.left==null||root.val==root.left.val-1)?left.decLen+1:1;
int decRight = (root.right==null || root.val==root.right.val-1)?right.decLen+1:1;
max = Math.max(max, incLeft+decRight-1);
max = Math.max(max, incRight+decLeft-1);
return new Entity(Math.max(incLeft, incRight), Math.max(decLeft, decRight));
}
}
Most Frequent Subtree Sum
没啥好说的, bottom up (left, right, root) dfs加HashMap, 一次AC
public class Solution {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int max = 0;
public int[] findFrequentTreeSum(TreeNode root) {
if(root==null) return new int[0];
dfs(root);
ArrayList<Integer> ans = new ArrayList<Integer>();
for(Integer key : map.keySet()){
System.out.println(key + " " + map.get(key));
if(map.get(key)==max) ans.add(key);
}
int[] a = new int[ans.size()];
for(int i=0;i<ans.size();i++)
a[i] = ans.get(i);
return a;
}
public int dfs(TreeNode root){
if(root==null) return 0;
int left = dfs(root.left);
int right = dfs(root.right);
int sum = left+right+root.val;
map.put(sum, map.getOrDefault(sum, 0)+1);
max = Math.max(max, map.get(sum));
return sum;
}
}
Convert BST to Greater Tree
右中左顺序的reverse inorder traversal
public class Solution {
public TreeNode convertBST(TreeNode root) {
if(root==null) return null;
TreeNode cur = root;
int prevSum = 0;
Stack<TreeNode> stack = new Stack<TreeNode>();
while(!stack.isEmpty() || cur!=null){
if(cur!=null){
stack.push(cur);
cur = cur.right;
}
else{
cur = stack.pop();
cur.val+=prevSum;
prevSum = cur.val;
cur = cur.left;
}
}
return root;
}
}