今�Hの国の呵呵君: [Algorithm]Get Paths with Given Sum in Binary Tree

今�Hの国の呵呵君: [Algorithm]Get Paths with Given Sum in Binary Tree

根据target得到所有path，path可以在任意一个节点开始和结束。和path with max sum类似，不过我们每次递归要返回的是子树里的所有path，为了避免不必要的计算，我们发挥所有path的时候也同时返回所有对应path的sum，所以我们新定义一个类result。在一个节点的时候，我们先递归左子树和右子树找到左子树和右子树中的的所有path，然后进行一下三种操作：

• 首先看当前node.val是不是等于target，如果是的话，当前node加入结果集，path只有当前node
• 然后看当前node和左子树return回来的每一条path能不能组成sum == target的path，能的话加入结果集
• 当前node和右子树return回来的每一条path能不能组成sum == target的path，能的话加入结果集
• 最后看左子树的每一条path和右子树的每一条path和当前node能不能组成sum == target的path，能的话加入结果集

不考虑加入结果集的时间，由于return回来的子树的path数为O(N^2)，因为两个node可以决定一条path，前三个都可以在O(N^2)时间完成，最后一步归根到底就是Two Sum的问题，也可以在O(N^2)时间完成。加入结果的时间取决于结果的多少k，path长度O(log n)，所以加入结果集的时间为O(k log n)。

最后注意把左边所有path右边path和当前node merge一下，return所有已当前node为root的subtree的所有path，记得加上当前node自己。这一步也是O(N^2)的，所以T(N) = 2T(N/2) + O(N^2)，根据master theorem，时间复杂度为O(N^2)。计算所需要的空间，所有path数量是N^2，因为两个node可以决定一条path，path的长度是O(log N)，所以空间复杂度是O(N^2 * log N)

    private class Result {
        private ArrayList<ArrayList<Integer>> paths;
        private ArrayList<Integer> sums;

        public Result() {
            paths = new ArrayList<ArrayList<Integer>>();
            sums = new ArrayList<Integer>();
        }

        public Result(ArrayList<ArrayList<Integer>> paths, ArrayList<Integer> sums) {
            this.paths = paths;
            this.sums = sums;
        }
    }

    private ArrayList<ArrayList<Integer>> res;

    public ArrayList<ArrayList<Integer>> getPaths(TreeNode root, int target) {
        res = new ArrayList<ArrayList<Integer>>();
        getPathsInSubTree(root, target);
        return res;
    }


    private Result getPathsInSubTree(TreeNode node, int target) {
        if (node == null)
            return new Result();
        Result left = getPathsInSubTree(node.left, target);
        Result right = getPathsInSubTree(node.right, target);
        ArrayList<Integer> leftSums = left.sums;
        ArrayList<Integer> rightSums = right.sums;
        ArrayList<ArrayList<Integer>> leftPaths = left.paths;
        ArrayList<ArrayList<Integer>> rightPaths = right.paths;
        //find qualified path
        //current node
        if (node.val == target) {
            ArrayList<Integer> temp = new ArrayList<Integer>();
            temp.add(node.val);
            res.add(temp);
        }
        //curr node and path from left subtree
        int leftLen = leftSums.size();
        for (int i = 0; i < leftLen; i++) {
            if (leftSums.get(i) == target - node.val) {
                ArrayList<Integer> temp = new ArrayList<Integer>(leftPaths.get(i));
                temp.add(node.val);
                res.add(temp);
            }
        }
        //curr node and path from right subtree
        int rightLen = rightSums.size();
        for (int i = 0; i < rightLen; i++) {
            if (rightSums.get(i) == target - node.val) {
                ArrayList<Integer> temp = new ArrayList<Integer>(rightPaths.get(i));
                temp.add(node.val);
                res.add(temp);
            }
        }
        //curr and path from left and path from right, actually two sum problem
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
        for (int i = 0; i < rightLen; i++) {
            if (!map.containsKey(rightSums.get(i))) {
                ArrayList<Integer> temp = new ArrayList<Integer>();
                temp.add(i);
                map.put(rightSums.get(i), temp);
            } else {
                map.get(rightSums.get(i)).add(i);
            }
        }
        for (int i = 0; i < leftLen; i++) {
            if (map.containsKey(target - node.val - leftSums.get(i))) {
                ArrayList<Integer> indexes = map.get(target - node.val - leftSums.get(i));
                int size = indexes.size();
                for (int j = 0; j < size; j++) {
                    ArrayList<Integer> rightPath = rightPaths.get(indexes.get(j));
                    //merge left curr and right
                    ArrayList<Integer> temp = new ArrayList<Integer>(leftPaths.get(i));
                    temp.add(node.val);
                    for (int k = rightPath.size() - 1; k >= 0; k--)
                        temp.add(rightPath.get(k));
                    res.add(temp);
                }
            }
        }
        //merge paths and return
        for(int i = 0; i < leftLen; i++) {
            leftSums.set(i, leftSums.get(i) + node.val);
            leftPaths.get(i).add(node.val);
        }
        for (int i = 0; i < rightLen; i++) {
            rightSums.set(i, rightSums.get(i) + node.val);
            rightPaths.get(i).add(node.val);
        }
        ArrayList<ArrayList<Integer>> retPaths = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> retSums = new ArrayList<Integer>();
        for(int i = 0; i < leftLen; i++) {
            retPaths.add(leftPaths.get(i));
            retSums.add(leftSums.get(i));
        }
        for (int i = 0; i < rightLen; i++) {
            retPaths.add(rightPaths.get(i));
            retSums.add(rightSums.get(i));
        }
        ArrayList<Integer> currPath = new ArrayList<Integer>();
        currPath.add(node.val);
        retPaths.add(currPath);
        retSums.add(node.val);
        return new Result(retPaths, retSums);
    }

    //for test use, serialize path
    public String serialize(ArrayList<ArrayList<Integer>> paths) {
        int size = paths.size();
        String res = "#";
        for (int i = 0; i < size; i++) {
            int len = paths.get(i).size();
            for (int j = 0; j < len; j++) {
                if (j == 0)
                    res += paths.get(i).get(j);
                else
                    res += "," + paths.get(i).get(j);
            }
            res += "#";
        }
        return res;
    }
Related: LeetCode - Path Sum II
Read full article from 今�Hの国の呵呵君: [Algorithm]Get Paths with Given Sum in Binary Tree