leetcode-113-Path-Sum-II

发表于   |  

描述

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

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

Return:

1
2
3
4
[
   [5,4,11,2],
   [5,8,4,5]
]

分析

在一颗二叉树中找出所有节点值的和等于 sum 的路径。深度优先遍历。

解决方案1（Python）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        result = list()
        path = list()
        
        def dfs(root, target):
            if not root:
                return
            path.append(root.val)
            target -= root.val
            if not root.left and not root.right and target == 0:
                result.append(path[:])
            dfs(root.left, target)
            dfs(root.right, target)
            path.pop()
        dfs(root, targetSum)
        return result

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<List<Integer>> result  = new LinkedList<List<Integer>>();
    
    public List<List<Integer>> pathSum(TreeNode root, int sum){
        List<Integer> equalPath  = new LinkedList<Integer>();
        recursion(root, sum, equalPath);
        return result;
    }
    
    public void recursion(TreeNode root, int sum, List<Integer> equalPath) {
        if (root == null) {
            return;
        }
        equalPath.add(new Integer(root.val));
        if (root.val == sum && root.left == null && root.right == null) {
            result.add(new LinkedList(equalPath));
        } else {
            recursion(root.left, sum-root.val, equalPath);
            recursion(root.right, sum-root.val, equalPath);
        }
        equalPath.remove(equalPath.size()-1);
    }
}

解决方案2（Golang）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, targetSum int) [][]int {
    result := [][]int{}
    path := []int{}
    dfs(&result, root, path, targetSum)
    return result
}

func dfs(result *[][]int, root *TreeNode, path []int, target int) {
    switch {
    case root == nil:
        return
    case root.Left == nil && root.Right == nil && root.Val == target:
        now := make([]int, len(path)+1)
        copy(now, append(path, root.Val))
        *result = append(*result, now)
        return
    }
    path = append(path, root.Val)
    dfs(result, root.Left, path, target-root.Val)
    dfs(result, root.Right, path, target-root.Val)
}

相关问题

题目来源