题解 | #二叉树中和为某一值的路径#

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        # 定义返回列表
        res = []
        
        def dfs(root, target, tmp):
            if not root:
                return
            # 判断搜索终止条件，达到叶节点停止
            if target == root.val and not root.left and not root.right:
                tmp += [root.val]
                res.append(tmp)
            # 递归左子树搜索
            if root.left:
                dfs(root.left, target-root.val, tmp + [root.val])
            # 递归右子树搜索
            if root.right:
                dfs(root.right, target-root.val, tmp + [root.val])
        # 深度优先搜索
        dfs(root, expectNumber, [])
        return res

import java.util.ArrayList;
import java.util.LinkedList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    //初始化集合
    ArrayList res = new ArrayList<>();
    LinkedListpath = new LinkedList<>(); 
    public ArrayList FindPath(TreeNode root,int target) {
        dfs(root, target);
        return res;
    }
    
    public void dfs(TreeNode root,int tar){
        
        if(root == null){
            return;
        }
        //将root节点放入路径集合
        path.add(root.val);
        //更新目标值，每放入一个节点，目标值应该相应减去对应节点的值，直到目标值为0
        tar -= root.val;
        //如果目标值减到了0 && 左节点为空 && 右节点为空 证明树已遍历完，此路径为目标路径
        if(tar==0 && root.left == null && root.right == null){
            res.add(new ArrayList(path));
        }
        // 递归左右子树
        dfs(root.left, tar);
        dfs(root.right, tar);
        //删除当前节点，在回溯过程中，此节点不在新路径上
        path.removeLast();
    }
}

复杂度分析：