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

问题陈述

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例:
给定如下二叉树，以及目标和 sum = 22。

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1

思路分析

对每一层进行递归迭代，下一次的sum为sum减去当前已访问结点值。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class solution {
    LinkedList<List<Integer>> list=new LinkedList<>();
    LinkedList<Integer> path=new LinkedList<>();
    public List<List<Integer> pathSum(TreeNode root){
        recurr(root,sum);
        return list;
        
    }
    public void recurr(TreeNode root,int res){
        if(root==null) return;
        path.add(root.val);
        res-=root.val;
        if(res==0&&root.left==null&&root.right==null)
            list.add(new LinkedList<>(path));
        recurr(root.left,res);
        recurr(root.right,res);
        path.removeLast();
    }
}