Shulou(Shulou.com)06/01 Report--

This article introduces you how to find the python binary tree path and, the content is very detailed, interested friends can refer to, hope to be helpful to you.

Given a binary tree and a target sum, it is determined whether there is a path from the root node to the leaf node in the tree, and the sum of all node values on this path is equal to the target sum.

Note: a leaf node is a node that does not have child nodes.

Example:

Given the following binary tree, and the target and sum = 22

five

/\

4 8

/ /\

11 13 4

/\\

7 2 1

Return true because there is a path 5-> 4-> 11-> 2 from the root node to the leaf node with a target and 22.

Ideas for solving the problem:

1, the binary tree type problem is usually a recursive solution.

2, there are two kinds of recursion: from the root down and from the leaf up

3. For the same type of problem and the maximum problem, the idea of solving the problem is opposite, this problem adopts from root to down.

/ * Definition for a binary tree node. * type TreeNode struct {* Val int * Left * TreeNode * Right * TreeNode * * / func hasPathSum (root * TreeNode, sum int) bool {if root==nil {return false} if root.Left==nil & & root.Right==nil {return root.Val==sum} return hasPathSum (root.Left,sum-root.Val) | | hasPathSum (root.Right,sum-root.Val)}

Given a binary tree and a goal sum, find all paths from the root node to the leaf node whose sum is equal to the given goal sum.

Note: a leaf node is a node that does not have child nodes.

Example:

Given the following binary tree, and the target and sum = 22

five

/\

4 8

/ /\

11 13 4

/ /

7 2 5 1

Return:

[

[5,4,11,2]

[5,8,4,5]

]

Train of thought:

1, which is also recursive, you need to save and pass on the path each time, and return if the condition is met, otherwise give up.

2. Note that the slice and map are passed by golang. Although the len of slice is passed each time, the data address is the same, so it will be overwritten, and the data result is different each time.

3. Copy the copy function for the solution.

/ * Definition for a binary tree node. * type TreeNode struct {* Val int * Left * TreeNode * Right * TreeNode * * / func pathSum (root * TreeNode, sum int) [] [] int {var r [] [] int if root = = nil {return r} var temp [] int return walk (root,sum,temp)}

Func walk (root * TreeNode, sum int,temp1 [] int) ([] [] int) {var r [] int if root==nil {return r} temp:=make ([] int,len (temp1)) copy (temp,temp1) temp=append (temp,root.Val) / / fmt.Println (root,temp,sum) if root.Left==nil & & root.Right==nil {if root.Val==sum {r=append (r) Temp) / / fmt.Println (root,temp,sum,r) return r} return r} tl:=walk (root.Left,sum-root.Val,temp) tr:=walk (root.Right,sum-root.Val,temp)

If len (tl) > 0 {r=append (rmagnetic tl.)} if len (tr) > 0 {r=append (rforce tr.)} return r} about how to find the path of python binary tree and that's it. I hope the above content can be helpful to everyone and learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.