113.路径总和2.md

113. 路径总和 II

url

题目

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

方法

可递归，当然也可迭代

code

js

let pathSum = (root, sum) => {
    let ret = []
    let dfs = (node, sum, list) => {
        if (node === null)
            return;
        list.push(node.val);
        sum -= node.val;
        if (sum === 0 && node.left === null && node.right === null) {
            ret.push(list.slice())
        } else {
            dfs(node.left, sum, list);
            dfs(node.right, sum, list);
        }
        list.pop();
    }
    dfs(root, sum, []);
    return ret;
}

go

func pathSum(root *TreeNode, targetSum int) [][]int {
	var ret [][]int
	var dfs func(node *TreeNode, sum int, list []int)
	dfs = func(node *TreeNode, sum int, list []int) {
		if node == nil {
			return
		}
		list = append(list, node.Val)
		sum -= node.Val
		if sum == 0 && node.Left == nil && node.Right == nil {
			ret = append(ret, append([]int{}, list...))
		} else {
			dfs(node.Left, sum, list)
			dfs(node.Right, sum, list)
		}
		list = list[:len(list)-1]
	}
	dfs(root, targetSum, []int{})
	return ret
}

java

class Solution {
    private List<List<Integer>> ret = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        
        dfs(root, sum, new ArrayList<Integer>());
        return ret;
    }

    private void dfs(TreeNode node, int sum, ArrayList<Integer> list) {
        if (node == null)
            return;
        list.add(node.val);
        sum -= node.val;
        if (sum == 0 && node.left == null && node.right == null)
            ret.add(new ArrayList(list));
        else {
            dfs(node.left, sum, list);
            dfs(node.right, sum, list);
        }
        list.remove(list.size() - 1);
    }
}