- 2020-08-12 11:01
*views 1*- Python

The first 13 day

2020.07.07 Tuesday

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 ——————————

solution ：

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 .

code ：

（ 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

Technology

Daily Recommendation

views 26

views 2

©2019-2020 Toolsou All rights reserved,

One is called “ Asking for the train ” A small village Finally got the train Spring Boot Lesson 16 ：SpringBoot Implementation of multithreading with injection class Chrome OS, For programmers and Windows What does it mean ? Internet Marketing JAVA Convert a string to a numeric type I've been drinking soft water for three years ? What is the use of soft water and water softener You don't know ——HarmonyOS Talking about uni-app Page value transfer problem JavaScript Medium Call and ApplySparkSQL Achieve partition overlay write Character recognition technology of vehicle license plate based on Neural Network