472. 두 갈래 나무의 경로와 III

        1
       / \
      2   3
     /
    4

    [
      [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> binaryTreePathSum3(ParentTreeNode root, int target) {
        List> results = new ArrayList>();
        dfs(root, target, results);
        return results;
    }
    
    public void dfs(ParentTreeNode root, int target, List> results) {
        if (root == null) {
            return;
        }

        List path = new ArrayList();
        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 path, 
                        List> 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);
    }
}