I tried LeetCode every day 112. Path Sum (Python, Go)

What is Leetcode

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)

27th question (problem 112)

  1. Path Sum

the issue's details

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.

Way of thinking

  1. Use recursive processing

  2. Dive into root left and right respectively, subtract val from the target Sum given as an argument, and return when it reaches 0.

  3. 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

I tried LeetCode every day 112. Path Sum (Python, Go)
I tried LeetCode every day 1. Two Sum (Python, Go)
I tried LeetCode every day 20. Valid Parentheses (Python, Go)
I tried LeetCode every day 136. Single Number (Python, Go)
I tried LeetCode every day 118. Pascal's Triangle (Python, Go)
I tried LeetCode every day 125. Valid Palindrome (Python, Go)
I tried LeetCode every day 155. Min Stack (Python, Go)
I tried LeetCode every day 9. Palindrome Number (Python, Go)
I tried LeetCode every day 141. Linked List Cycle (Python, Go)
I tried LeetCode every day 110. Balanced Binary Tree (Python, Go)
I tried LeetCode every day 14.Longest Common Prefix (Python, Go)
I tried LeetCode every day 119. Pascal's Triangle II (Python, Go)
I tried LeetCode every day 21. Merge Two Sorted Lists (Python, Go)
I tried LeetCode every day 168. Excel Sheet Column Title (Python, Go)
I tried LeetCode every day 167. Two Sum II --Input array is sorted (Python, Go)
I tried LeetCode every day 111. Minimum Depth of Binary Tree (Python, Go)
I tried LeetCode every day 26. Remove Duplicates from Sorted Array (Python, Go)
I tried LeetCode every day 160. Intersection of Two Linked Lists (Python, Go)
I tried LeetCode every day 108. Convert Sorted Array to Binary Search Tree (Python, Go)
I tried LeetCode every day 122. Best Time to Buy and Sell Stock II (Python, Go)
I tried Grumpy (Go running Python).
I tried running faiss with python, Go, Rust
I tried Python> decorator
I tried fp-growth with python
I tried scraping with Python
I tried Python C extension
[Python] I tried using OpenPose
I tried gRPC with Python
I tried scraping with python
I tried to touch Python (installation)
I tried web scraping with python.
I tried using Thonny (Python / IDE)
I tried running prolog with python 3.8.2.
I tried Line notification in Python
I tried SMTP communication with Python
[Python] I tried using YOLO v3
I tried to summarize Python exception handling
I tried to implement PLSA in Python
I tried to implement permutation in Python
I tried scraping Yahoo News with Python
I tried to implement PLSA in Python 2
Python3 standard input I tried to summarize
I tried sending an email with python.
I tried using Bayesian Optimization in Python
I tried non-photorealistic rendering with Python + opencv
I tried using UnityCloudBuild API from Python
I tried to implement ADALINE in Python
I tried a functional language with Python
I tried recursion with Python ② (Fibonacci sequence)
I tried to implement PPO in Python
Python: I tried the traveling salesman problem
Wrangle x Python book I tried it [1]
Mayungo's Python Learning Episode 8: I tried input
[Python] I tried to calculate TF-IDF steadily
I tried scraping Yahoo weather (Python edition)
I tried to touch Python (basic syntax)
I tried the Python Tornado Testing Framework
#I tried something like Vlookup with Python # 2
[LIVE] I tried to deliver the sunrise and sunset times nationwide every day
Python day 1
[Baseball Hack] I tried copying the Python MLB score & grade data acquisition script with Go in half a day