Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

Problem description

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 root to leaf represents a number: for example, path 1 -> 2 -> 3 from root to leaf represents the number 123. Computes the sum of all numbers generated from the root node to the leaf node.

Example:

Enter: root = [1,2,3]

Output: 25

Explanation: Root-to-leaf path 1->2 represents the number 12, and root-to-leaf path 1->3 represents the number 13, so the sum of the numbers = 12 + 13 = 25.

To analyze problems

Each node has a number equal to the number of its parent node times 10 plus the value of the node. Just calculate the numbers for all the leaf nodes and sum them to get the result. Iterate to find the corresponding numbers of all leaf nodes, we can use depth-first search and breadth-first search to achieve.

Depth-first search

Each node is traversed from the root node, and if a leaf node is encountered, the number corresponding to the leaf node is added to the result. If a non-leaf node is encountered, the value of that node is computed and its children are recursively traversed.

Class Solution: def sumNumbers(self, root): def DFS (root, pre): Return 0 total = pre * 10 + root.val # if not root.left and not root.right: return total else: Return DFS (root.left, total) + DFS (root.right, total)Copy the code

The time complexity and space complexity of this algorithm are O(n).

Breadth-first search

To solve this problem using breadth-first search, we need to maintain two queues to store the nodes and their corresponding numbers. We start by adding the root node and its corresponding value to two separate queues. If the queue is not empty, we take a node and a number from each queue and do the following:

  • If the current node is a leaf node, we add the number corresponding to that node to the result.
  • If the current node is not a leaf node, the non-empty child node of the current node is added to the queue, and the number represented by the child node is calculated according to the number corresponding to the current node and its child node, and the number is added to the queue.

After the search, the sum of the numbers corresponding to all the leaf nodes can be obtained.

Let’s take a look at the code implementation.

Import collections class Solution: def sumNumbers(self, root): NodeQueue = collections.deque([root]) numQueue = collections.deque([root.val]) # If the queue is not empty while nodeQueue: Numqueue.popleft () num = numqueue.popleft () left, right = node.left, node. If not left and not right: total += num else: # nodeQueue.append(left) numQueue.append(num * 10 + left.val) if right: nodeQueue.append(right) numQueue.append(num * 10 + right.val) return totalCopy the code

The time complexity and space complexity of this algorithm are O(n).