“This is the 21st day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

Brush algorithm, is never to memorize the problem, but to practice the actual problem into a concrete data structure or algorithm model, and then use the corresponding data structure or algorithm model to solve the problem. In my opinion, with this kind of thinking, I can not only solve the interview problems, but also learn to think in daily work. How to abstract the actual scene into the corresponding algorithm model, so as to improve the quality and performance of the code

Find the sum of the numbers from the root to the leaf

Find the sum of the numbers from the root to the leaf

Topic describes

You are given the root node of a binary tree. Each node in the tree contains a number between 0 and 9

Each path from the root node to the leaf node represents a number:

  • For example, the path from the root node to the leaf node1 -> 2 -> 3Represent Numbers123

Computes the sum of all numbers generated from the root node to the leaf node

Leaf nodes are nodes that have no children

The sample

Example 1

Input: root = [1,2,3] Output: 25 Description: The path from the root to the leaf node 1->2 represents the number 12. The path from the root to the leaf node 1->3 represents the number 13Copy the code

Example 2

Input: root = [4,9,0,5,1] output: 1026 The path from the root to the leaf node 4->9->5 represents the number 495. The path from the root to the leaf node 4->9->1 represents the number 491. The path from the root to the leaf node 4->0 represents the number 40Copy the code

Tip:

  • The number of nodes in the tree is in the range[1, 1000] 内
  • 0 <= Node.val <= 9
  • The depth of the tree does not exceed10

The problem solving

Solution 1: depth-first search

Train of thought

And the easiest way to think about this problem is, if I can go from left to right, or right to left, and get the number on each path, if I go from left to right, if I find it or not, it’s pre-order traversal

The idea of front-order traversal is consistent with the idea of depth-first search, that is, when one road goes dark and there is no road, it takes a step back and finds another way to continue. The following is how to implement it

The first thing we can find is that we can calculate the number represented by the child node according to the value of the current node and the value of the child node (left child node or right child node), that is: the number of the child node = the value of the parent node *10 + the value of the child node

  • If the current node has no children, that is, if it is itself a leaf node, the number of the current node can be returned directly
  • If the current node is a non-leaf node, its number is the sum of the numbers of the left and right child nodes

code

Func (root *TreeNode) int {return DFS (root, 0)} func DFS (root *TreeNode, preNodeVal int) int { if root == nil { return 0 } num := preNodeVal * 10 + root.Val if root.Left == nil && root.Right ==  nil { return num } return dfs(root.Left, num) + dfs(root.Right, num) }Copy the code

Solution two: breadth-first search

Train of thought

Almost any problem that can be solved with depth-first search can be solved with breadth-first search (and vice versa)

The core idea of breadth-first search is to search all the nodes closest to the starting point first, and then search the nodes closest to 7 times. In fact, on a binary tree, it’s a sequence traversal

With the above basic idea is the same, the value of each node is calculated in the same way. We just need queues to help us do that. We need two queues, one for each node, and one for the number of each node

If no node is removed from the queue, repeat the following steps

  • If the node taken out is a leaf node, add the node’s numbers to the sum
  • If it’s not a leaf node, it calculates the number of the child node based on the value of the current node and the value of the child node. The child node and the number corresponding to the child node are then placed in the queue

If you look at the code, it’s easy to understand

code

// Breadth-first search func sumNumbers2(root *TreeNode) int {if root == nil {return 0} nodeQueue := []*TreeNode{root} numQueue := []int{root.Val} sum := 0 for len(nodeQueue) ! = 0 { node := nodeQueue[0] if len(nodeQueue) > 1 { nodeQueue = nodeQueue[1:] } else { nodeQueue = []*TreeNode{} } num :=  numQueue[0] if len(numQueue) > 1 { numQueue = numQueue[1:] } else { numQueue = []int{} } leftNode, rightNode := node.Left, node.Right if leftNode == nil && rightNode == nil { sum += num } else { if node.Left ! = nil { nodeQueue = append(nodeQueue, node.Left) numQueue = append(numQueue, num * 10 + node.Left.Val) } if node.Right ! = nil { nodeQueue = append(nodeQueue, node.Right) numQueue = append(numQueue, num * 10 + node.Right.Val) } } } return sum }Copy the code