算法题--判断一棵二叉树是否有分支元素之和为指定值

image.png

0. 链接

题目链接

1. 题目

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path 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      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

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

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

3. 代码

# coding:utf8


# 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 hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if root is None:
            return False

        queue = [(root, sum - root.val)]
        while len(queue) > 0:
            size = len(queue)
            for i in range(size):
                node, cur_sum = queue.pop(0)
                if node.left is None and node.right is None:
                    if cur_sum == 0:
                        return True
                if node.left is not None:
                    queue.append((node.left, cur_sum - node.left.val))
                if node.right is not None:
                    queue.append((node.right, cur_sum - node.right.val))

        return False


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.right = TreeNode(1)
print(solution.hasPathSum(root1, 22))

输出结果

True

4. 结果

image.png