leetcode.com This is the practice of coding interviews for software developers. A total of more than 1,500 coding questions have been posted, and it seems that the same questions are often asked in actual interviews.
Introduction to golang + algorithm I will solve it with go and Python to strengthen the brain. (Python is weak but experienced)
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.
(Japanese translation)
Given a binary tree and a sum, determine if the tree has a root-to-leaf path so that the sum of all values along the path is equal to the given sum.
** Note: ** Leaf is a childless node.
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.
Use recursive processing
Dive into root left and right respectively, subtract val from the target Sum given as an argument, and return when it reaches 0.
Finally, true if the first root left or right has a correct answer, false is returned if neither has a correct root.
Answer code
class Solution:
def hasPathSum(self, root, sum):
if not root:
return False
if not root.left and not root.right and root.val == sum:
return True
sum -= root.val
return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)
--I'll write it in Go too!
func hasPathSum(root *TreeNode, sum int) bool {
if root == nil {
return false
}
if root.Left == nil && root.Right == nil {
return sum == root.Val
}
return hasPathSum(root.Left, sum-root.Val) || hasPathSum(root.Right, sum-root.Val)
}
#### **`I tried Leet Code every day 111. Minimum Depth of Binary Tree（Python、Go）`**
``` Minimum Depth of Binary Tree（Python、Go）
Recommended Posts