The first 13 day
Today is the day of college entrance examination for senior three students , I'm a junior and I'm a hammer .
Degree of Difficulty ： simple
subject ：112 Sum of paths
Given a binary tree and a target sum , Determine whether there is a path from root node to leaf node in the tree , The sum of the values of all nodes on this path is equal to the sum of the targets .
explain : A leaf node is a node that has no children .
Examples : Given the following binary tree , And goals and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 return true,
Because there are goals and 22 The path from the root node to the leaf node of 5->4->11->2.
—————————— I am the dividing line ——————————
thinking ： Deep search
so-called DFS Depth first search , But don't hit the south wall and don't look back . Go straight down , If you can't make it, you can go back and take another way .
The essence of deep search is exhaustion , Try in a certain order , Until we find the solution to the problem .
（ The code I put here is the code I tested by the compiler ）
# leetcode112 Sum of paths 2020.07.07 # Definition for a binary tree node. class
TreeNode(object): def __init__(self, x,left=0,right=0): self.val = x self.left =
left self.right = right class Solution(object): def hasPathSum(self, root, sum)
: """ :type root: TreeNode :type sum: int :rtype: bool """ if not root:
# If the node is empty, return False return False if not root.left and not root.right: # The left and right subtrees are empty This is the leaf node
return sum==root.val # judge sum Is equal to the value of the current node return self.hasPathSum(root.left,sum-root.
val) or self.hasPathSum(root.right,sum-root.val) tree1=TreeNode(7) tree2=
TreeNode(2) tree3=TreeNode(1) tree4=TreeNode(4,0,tree3) tree5=TreeNode(13) tree6
=TreeNode(11,tree1,tree2) tree7=TreeNode(4,tree6) tree8=TreeNode(8,tree5,tree4)
root=TreeNode(5,tree7,tree8) sum = 22 print(Solution().hasPathSum(root,sum))
# result True