题解 | #二叉树中和为某一值的路径(一)#

from enum import Flag
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param sum int整型 
# @return bool布尔型
#
class Solution:
    def hasPathSum(self , root: TreeNode, s: int) -> bool:
        # write code here
        res = [] # 尝试用更少的空间
        if not root:
            return False
        flag = [False]
        def backtrace(root): # 递归搜索
            res.append(root.val)
            if not root.left and not root.right: # 如果搜到叶子节点
                if sum(res) == s: # 判断和等不等
                    flag=True
                    return
            if root.left:
                backtrace(root.left) # 左递归
                if not flag[0]:
                    res.pop() # 回溯
                else:
                    return
            if root.right:
                backtrace(root.right) # 右递归
                if not flag[0]:
                    res.pop() # 回溯
                else:
                    return

        backtrace(root)
        return flag[0]





        ''' # 以下是两个栈的O（n）复杂度解法
        if not root:
            return False
        from collections import deque
        DQ = deque([root])
        PATH = deque([[root.val]])

        while DQ:
            cur = DQ.popleft()
            cur_path = PATH.popleft()
            if sum(cur_path) == s and not cur.left and not cur.right:
                return True
            if cur.left:
                DQ.append(cur.left)
                PATH.append(cur_path + [cur.left.val])
            if cur.right:
                DQ.append(cur.right)
                PATH.append(cur_path + [cur.right.val])

        return False
        '''