472.二叉树的路径和 III

描述

给一棵二叉树和一个目标值，找到二叉树上所有的和为该目标值的路径。路径可以从二叉树的任意节点出发，任意节点结束。

样例

给一棵这样的二叉树：

        1
       / \
      2   3
     /
    4

和目标值 target = 6。你需要返回的结果为：

    [
      [2, 4],
      [2, 1, 3],
      [3, 1, 2],
      [4, 2]
    ]

思路

遍历所有可能的点，把当前点当成拐点，左子树的每条路径和与当前点的值以及右子树的每条路径和分别组合起来构成了当前结点的全部路径

代码

/**
 * Definition of ParentTreeNode:
 * 
 * class ParentTreeNode {
 *     public int val;
 *     public ParentTreeNode parent, left, right;
 * }
 */
public class Solution {
    /**
     * @param root the root of binary tree
     * @param target an integer
     * @return all valid paths
     */
    public List<List<Integer>> binaryTreePathSum3(ParentTreeNode root, int target) {
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        dfs(root, target, results);
        return results;
    }
    
    public void dfs(ParentTreeNode root, int target, List<List<Integer>> results) {
        if (root == null) {
            return;
        }

        List<Integer> path = new ArrayList<Integer>();
        findSum(root, null, target, path, results);
·   
        dfs(root.left, target, results);
        dfs(root.right, target, results);
    }

    public void findSum(ParentTreeNode root, 
                        ParentTreeNode father, 
                        int target,
                        List<Integer> path, 
                        List<List<Integer>> results) {
        path.add(root.val);
        
        target -= root.val;
        if (target == 0) {
            results.add(new ArrayList(path));
        }
        
        // 类似图遍历算法，往 left、right、parent 三个方向遍历，
        // 通过判断 parent 指针是否等于 father 来判断是否出现往回遍历的情形
        // 当前结点指针往上遍历时，下一轮递归 root.parent 做根结点同样往三个方向遍历，如果往下就可能出现重复
        // 判断条件就是防止出现这种情况
        if (root.parent != null && root.parent != father) {
            findSum(root.parent, root, target, path, results);
        }

        if (root.left != null && root.left  != father) {
            findSum(root.left, root, target, path, results);
        }

        if (root.right != null && root.right != father) {
            findSum(root.right, root, target, path, results);
        }

        path.remove(path.size() - 1);
    }
}