- 2020-08-12 11:01
*views 2*- 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

- Java392 articles
- Python205 articles
- Linux110 articles
- Vue97 articles
- MySQL83 articles
- SpringBoot70 articles
- javascript65 articles
- Spring62 articles
- more...

Daily Recommendation

views 2

©2019-2020 Toolsou All rights reserved,

The 11th Blue Bridge Cup python The real topic of the University Group National Games JavaSwing To achieve a simple Lianliankan games 【Spring Source code analysis 】42-@Conditional Detailed explanation element-ui Step on pit record 2019PHP Interview questions （ Continuously updated ）PHPJava Misunderstanding —— Method overloading is a manifestation of polymorphism ? First issue 500 100 million , Set up a new Department , What is Tencent going to do ? Google chrome The browser can't open the web page , But what if other browsers can open it ? Regression of dependent variable order categories （R language ）【Golang Basic series 10 】Go language On conditional sentences if