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

Problem Description:

You are given a binary tree and are asked to return the values of nodes traversed in order. (That is, layer by layer, all nodes are accessed from left to right).

Example: binary tree: [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Return sequence traversal results: [[3],[9,20],[15,7]]

To analyze problems

Before we begin, let’s review what BFS (breadth first search) and DFS (depth first search) are.

  1. BFS: Breadth-first search starts with an unvisited vertex V in the graph, traverses the adjacent nodes of that node, and then traverses the adjacent nodes of each adjacent node, layer by layer.
  2. DFS: Depth-first search starts at an unvisited vertex V in the graph, goes all the way to the end, and then goes back from the node at the end of that path to the previous node, and starts the other way to the end… , recursively repeat this process until all vertices have been traversed. It is characterized by not hitting the south wall and not turning back. It first goes one way and then moves on another way.

Let’s take a look at the code implementation separately.

DFS traversal:

def dfs(root):
    if not root:
        return
    dfs(root.left)
    dfs(root.right)
Copy the code

BFS traversal:

def bfs(root):
    res = []
    if root: 
       queue = [root]
       while queue:
           node=queue.pop()
           res.append(node.val)
           if node.left:
               queue.append(node.left)
           if node.right:
               queue.append(node.right)
    
    return res
Copy the code

Now let’s look at the problem, and they want to traverse the binary tree in order. So what is sequential traversal? In simple terms, it’s layering a binary tree and traversing each level from left to right.

If you look at this, do you see that it’s the same order as BFS traversal. We can use BFS algorithm to get the result of sequence traversal directly. Note that there is a slight difference between the output of a sequence traversal and that of a BFS traversal. The order traversal requires us to differentiate each layer, that is, output a two-dimensional array. The output of the BFS traversal is a one-dimensional array, and there is no way to tell which layer it is, so we need to modify the BFS code slightly.

def bfs(root): if not root: return [] res = [] queue = [] queue.append(root) while queue: Size = len(queue) TMP = [] node = queue.pop(0) tmp.append(node.val) size = size - 1 if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(tmp) return resCopy the code

Complexity analysis.

  1. Time complexity: Each node in the binary tree enters and exits the queue once, so the time complexity is O(n).
  2. Spatial complexity: There are no more than n elements in the queue, so the spatial complexity is O(n).