1 # Definition for a binary tree node.
 2 # class TreeNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution:
 9     def hasPathSum(self, root: TreeNode, sum: int) -> bool: 
10         # #樹使用的是雙向鏈表
11         # #如果根節點為空，直接返回False
12         # if not root:
13         #     return False
14 
15         # #依次遍歷根節點，直到葉子節點：判定葉子節點的辦法：左葉子的孩子和右葉子的孩子均為None
16         # que_node = collections.deque([root])
17         # que_val_sum = collections.deque([root.val])
18         # while que_node:
19         #     node = que_node.popleft()  #從隊列中取出第一個節點
20         #     node_val = que_val_sum.popleft()  #取出第一個節點的元素
21         #     if not node.left and not node.right:
22         #         if node_val == sum:
23         #             return True
24         #         continue
25         #     #如果該節點左葉子存在，那么將左葉子直接加入隊列中；
26         #     #計算該節點的元素與孩子節點的值的和
27         #     if node.left:
28         #         que_node.append(node.left)
29         #         que_val_sum.append(node.left.val + node_val)
30         #     #同理左節點
31         #     if node.right:
32         #         que_node.append(node.right)
33         #         que_val_sum.append(node.right.val + node_val)
34         # return False
35 
36         #采用遞歸的方法
37         #如果該節點是葉子節點，那么直接判斷與sum的關系
38         if not root:
39             return False
40         if not root.left and not root.right:
41             return root.val == sum
42         return self.hasPathSum(root.left,sum - root.val) or self.hasPathSum(root.right,sum - root.val)