剑指 Offer 34. 二叉树中和为某一值的路径--dfs

剑指 Offer 34. 二叉树中和为某一值的路径--dfs

典型的dfs搜索回溯，没有剪枝，需要全部搜索

注意：将list和path设置为全局变量将整个传参简化了许多。

递归结束条件：

• 节点为空

递归体：

• target随着递归深入一直减小，当target为0时，找到一条路径
• dfs左子节点
• dfs右子节点
• 回溯时，将该子节点从路径中移除

class Solution {
    List> list = new linkedList();
    List path = new linkedList();
    public List> pathSum(TreeNode root, int target) {
            dfs(root, target);
            return list;
    }

    public void dfs(TreeNode node, int target){
        if(node == null)return;
        path.add(node.val);
        target -= node.val;
        if(target == 0 && node.left == null && node.right == null){
            list.add(new linkedList(path));
        }
        dfs(node.left,target);
        dfs(node.right,target);
        path.remove(path.size()-1);
    }
}