描述

給一棵二叉樹和一個目標值，找到二叉樹上所有的和為該目標值的路徑。路徑可以從二叉樹的任意節(jié)點出發(fā)，任意節(jié)點結束。

樣例

給一棵這樣的二叉樹：

        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 來判斷是否出現(xiàn)往回遍歷的情形
        // 當前結點指針往上遍歷時，下一輪遞歸 root.parent 做根結點同樣往三個方向遍歷，如果往下就可能出現(xiàn)重復
        // 判斷條件就是防止出現(xiàn)這種情況
        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);
    }
}