How to analyze the path Sum in python binary Tree
How to parse the path sum in python binary tree, I believe many inexperienced people are helpless about this, for this reason this article summarizes the causes and solutions of the problem, through this article I hope you can solve this problem.
Given a binary tree, each node of which stores an integer value.
Find the sum of paths equal to the total number of paths given.
The path does not need to start at the root node, nor does it need to end at the leaf node, but the path direction must be downward (only from the parent node to the child node).
The binary tree has no more than 1000 nodes, and the node value range is [-100000, 100000] integer.
Examples:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
Return to 3. The paths that sum to 8 are:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
Solution:
1, this problem can be broken down into subproblems: paths from the root node and the number of paths equal to a certain number
2. Sum up all the nodes as roots.
3, a path rooted at a node and including multiple cases
A, including subpaths with sum 0
B, excluding
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */func pathSum(root *TreeNode, sum int) int { count:=sumRoot(root,sum) if root!= nil{ count+=pathSum(root.Left,sum) count+=pathSum(root.Right,sum) } return count}
func sumRoot(root*TreeNode,sum int)int{ if root==nil{ return 0 } if root.Val==sum{ return 1 +sumRoot(root.Left,sum-root.Val)+sumRoot(root.Right,sum-root.Val) } return sumRoot(root.Left,sum-root.Val)+sumRoot(root.Right,sum-root.Val)} After reading the above contents, do you know how to parse the path sum in python binary tree? If you still want to learn more skills or want to know more related content, welcome to pay attention to the industry information channel, thank you for reading!
