【题目描述】

AcWing 47. 二叉树中和为某一值的路径

【思路】

遍历二叉树，记录走过路径的和，到达叶子结点时，如果 等于sum，就加入res链表中。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    int sum;
    public void dfs(TreeNode root, List<Integer> path, int ans){

        if(root == null) return;//上层没有左孩子节点或者没有右孩子节点
        //到达叶子结点 9的左右孩子均为空所以加了两次
        if( root.left == null && root.right == null){
            if( ans + root.val == sum) {//叶子结点要特殊处理一下
                path.add(root.val);
                res.add(path);
            }
            return;
        }
        List next = new ArrayList<Integer>(path);
        //引用调用，需要复制path内容，不然存在ans中的为引用
        next.add(root.val);
        dfs( root.left, next, ans + root.val);
        dfs( root.right, next, ans + root.val);

    }

    public List<List<Integer>> findPath(TreeNode root, int _sum) {
        sum = _sum;
        dfs(root, new ArrayList<Integer>(), 0);
        return res;

    }
}