Shulou(Shulou.com)05/31 Report--

In this article, the editor introduces in detail the "case Analysis of the Sum of C++ paths" with detailed contents, clear steps and proper handling of the details. I hope that this article "the Sum of C++ paths and case Analysis" can help you solve your doubts. Let's follow the editor's train of thought to slowly deepen, together to learn new knowledge.

Algorithm:

The algorithm uses recursion, and the core is how to find the termination condition of recursion. The specific steps are as follows:

1. In a recursive way, the value of sum decreases with the nodes that have been traversed, sum = sum-root.Val2. The recursive termination condition sum==0 is one of them, and if the requirement is a leaf node, you also need to add

Topic 1: summation of paths

Code implementation:

/ * 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} / / judgment of leaf nodes Exclude non-leaf nodes = = sum if root.Left = = nil & & root.Right = = nil {return sum = = root.Val} res: = sum-root.Val if hasPathSum (root.Left,res) {return true} if hasPathSum (root.Right,res) {return true} return false}

Topic 2: path Sum 2

Code implementation:

/ * Definition for a binary tree node. * type TreeNode struct {* Val int * Left * TreeNode * Right * TreeNode *} * / var res [] [] intfunc pathSum (root * TreeNode, sum int) [] [] int {res = [] [] int {} / / to clear the last res value if root = = nil {return nil} / / var res [] int var tmp [] int dfs (root,sum,tmp) return res} func dfs (root * TreeNode) Sum int, tmp [] int) {if root = = nil {return} tmp = append (tmp,root.Val) if sum = = root.Val & & root.Left = = nil & & root.Right = = nil {r: = make ([] int, len (tmp)) / / prevent tmp's shared content from being modified copy (r, tmp) res = append (res) R) return} dfs (root.Left,sum-root.Val,tmp) dfs (root.Right,sum-root.Val,tmp) return}

Topic 3: path Sum 3

Code implementation:

/ * Definition for a binary tree node. * type TreeNode struct {* Val int * Left * TreeNode * Right * TreeNode * * / func pathSum (root * TreeNode, sum int) int {if root = = nil {return 0} result: = countPath (root,sum) result + = pathSum (root.Left,sum) result + = pathSum (root.Right,sum) return result} func countPath (root * TreeNode) Sum int) int {if root = = nil {return 0} count: = 0 res: = sum-root.Val if res = = 0 {count = 1} return count + countPath (root.Left,res) + countPath (root.Right) Res)} / * the number of paths with the current node as the head node, the number of paths with the left child of the current node as the head node, and the right child of the current node as the head node * / read here The article "Sum of C++ paths and case Analysis" has been introduced. If you want to master the knowledge points of this article, you still need to practice and use it. If you want to know more about the article, please follow the industry information channel.

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.