路径和路径和

Binary Tree Paths

return all root-to-leaf paths.

注意：起点是root，而不是空集

public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        if(root == null) {
            return result;
        }
        dfs(root, result, root.val + "");
        return result;
    }

    public void dfs(TreeNode root, List<String> result, String path) {
        if(root == null) return;
        if(root.left == null && root.right == null) {
            result.add(path);
            return;
        }

        if(root.left != null) {
            dfs(root.left, result, path + "->" + root.left.val);
        }
        if(root.right != null) {
            dfs(root.right, result, path + "->" + root.right.val);
        }

    }
}

Path Sum II

find all root-to-leaf paths where each path's sum equals the given sum.

tree上的backtracking

这种找从根节点到叶子节点路径的题，最好把root作为backtracking的起点而不是空集。

public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null) {
            return result;
        }
        List<Integer> path = new ArrayList<>();
        // 起点是root 而不是空集
        path.add(root.val);
        dfs(root, sum - root.val, path, result);
        return result;
    }

    public void dfs(TreeNode root, int sum, List<Integer> path, List<List<Integer>> result) {
        if(root == null) return;
        // 到leaf节点的时候可以判断是否sum == 0
        if(sum == 0 && root.left == null && root.right == null) {
            // path.add(root.val);
            result.add(new ArrayList(path));
            return;
        }

        if(root.left != null) {
            path.add(root.left.val);
            dfs(root.left, sum - root.left.val, path, result);
            path.remove(path.size() - 1);
        }

        if(root.right != null) {
            path.add(root.right.val);
            dfs(root.right, sum - root.right.val, path, result);
            path.remove(path.size() - 1);
        }
    }
}

Binary Tree Maximum Path Sum

问题： 最优路径可能和root是不连续的

解法： 用全局变量

最大和路径有这么几种可能：

• 从 root 出发，路上看到负数，不采用；
• 从 root 出发，路上看到负数，负数后面存在总和超过负数节点的路径；
• 最大和在某个从 leaf node 往上走的一条路径上，不过 root.
• 左路径最大，采用左路径；
• 右路径最大，采用右路径；
• 单独节点最大，可能是 左/右/根 其中之一。

一个重要的问题是，我们只能从 root 开始，也没有 parent 指针，但是最优的路径可能却和 root 是不连续的，这就切断了 Binary Tree divide & conquer / Tree DFS 里面大多数做法中非常依赖的性质，即层层递归之前 左/右 子树和根节点的联系。

然而套路还是要用的，要么这题就没法做了。。好在问题没有要求返回具体 path ，只要一个 max sum 所以我们需要引入全局变量。

每一层的“三角形”路径都要和全局最优 update 一下，然而不是有效的 path. 最终 return 的结果只是“必须包括当前节点” 的最大 path，由此完成连续的递归结构（recurrence substructure）

另外一个小技巧是，在求 max sum 的情况下，每一个节点可以有 “选”（root.val） 或者 “不选” （0） 两种选择

我们可以把dfs传递的参数用一个wrapper class 包起来，可以作为全局变量来update

public class Solution {
    class Result {
        // 从root开始往下的一条path,可以不包含任何点
        int single;
        // 从任意点到任意点，必须包含一个点
        int max;
        public Result(int single, int max) {
            this.single = single;
            this.max = max;
        }
    }

    public int maxPathSum(TreeNode root) {
        Result result = dfs(root);
        return result.max;
    }

    public Result dfs(TreeNode root) {
        if(root == null) {
            return new Result(0, Integer.MIN_VALUE);
        }

        Result left = dfs(root.left);
        Result right = dfs(root.right);

        int single = Math.max(left.single, right.single);
        // single path是可以不经过任何点的，如果都为负数，就返回0
        single = Math.max(0, single + root.val);

        int max = Math.max(left.max, right.max);
        // 经过root的path 和不经过root的path进行比较
        max = Math.max(max, left.single + right.single + root.val);

        return new Result(single, max);
    }
}