路径与路径和

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;
    }
}

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);
    }
}

  • 5/27 号重做了一遍，这次的代码

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);

    }
}

112. Path Sum I

简化版，这次不用存所有的 Paths 了，套用 Tree DFS 模板可以，不过在只求 boolean / int 的情况下，也有更简单直接的写法。

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);
    } 
}

或者更直接点，

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

这题有点 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[] 当参数传就行了。

    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);

    }
Previous子树组合，BST queryNextNestedInteger 类

Last updated