112. 路徑總和

題目

使用廣度優(yōu)先搜索的方式，記錄從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑和。
使用兩個(gè)隊(duì)列，分別存儲(chǔ)將要遍歷的節(jié)點(diǎn)，以及根節(jié)點(diǎn)到這些節(jié)點(diǎn)的路徑和即可。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if root==None:
            return False
        nodestack = [root]
        sumstack = [root.val]
        while nodestack:
            p = nodestack.pop(0)
            cursum = sumstack.pop(0)
            
            if p.left:
                cur_left_sum = cursum + p.left.val
                nodestack.append(p.left)
                sumstack.append(cur_left_sum)
            if p.right:
                cur_right_sum = cursum + p.right.val
                nodestack.append(p.right)
                sumstack.append(cur_right_sum)

            if not p.left and not p.right:
                if cursum==sum:
                    return True
        return False