算法题--求一棵二叉树满足和为指定值的分支元素列表

image.png

0. 链接

题目链接

1. 题目

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,

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

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

2. 思路1: 利用队列+分层迭代

• 利用队列，队列中记录遍历到每层时的每个元素值和到目前位置剩余和
• 当遍历到一个叶子节点时, 发现剩余和为0，则收集一个符合条件的列表, 然后继续
• 遍历完全部分支，也没发现有满足要求的时，返回False
• 时间复杂度 O(N)
• 空间复杂度 O(N)

3. 代码

# coding:utf8
from typing import List


# 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: TreeNode, sum: int) -> List[List[int]]:
        rtn_list = list()
        if root is None:
            return rtn_list
        queue = [(root, sum - root.val, [root.val])]
        while len(queue) > 0:
            size = len(queue)
            for i in range(size):
                node, cur_sum, cur_list = queue.pop(0)
                if node.left is None and node.right is None:
                    if cur_sum == 0:
                        rtn_list.append(cur_list)
                if node.left is not None:
                    queue.append((node.left, cur_sum - node.left.val, cur_list + [node.left.val]))
                if node.right is not None:
                    queue.append((node.right, cur_sum - node.right.val, cur_list + [node.right.val]))

        return rtn_list


solution = Solution()

root1 = node = TreeNode(5)
node.left = TreeNode(4)
node.right = TreeNode(8)
node.left.left = TreeNode(11)
node.left.left.left = TreeNode(7)
node.left.left.right = TreeNode(2)
node.right.left = TreeNode(13)
node.right.right = TreeNode(4)
node.right.right.left = TreeNode(5)
node.right.right.right = TreeNode(1)
print(solution.pathSum(root1, 22))

输出结果

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

4. 结果

image.png