Algorithm Interview Replay: Binary Tree Traversal and BFS (bytes)

In the previous section, we learned about DFS (depth-first search) for binary trees, which is essentially traversing all the way down in one direction. Can we access the data in the tree level by level? Of course, this is BFS (width first search), also known as breadth first search.

We’re still going to do it by example.

01. Topic analysis

Example:

A given binary tree [3,9,20, null, null, 15, 7], 3/20 / \ \ 9 15 7 returns to its level traversal results: [[3], [9], [15, 7]]Copy the code

This series is a must!

02. Introduction to BFS

BFS, breadth/width first. It’s basically going from top to bottom, going through each layer and then going through the next layer. Suppose our tree looks like this:

According to BFS, the access order is as follows:

a->b->c->d->e->f->g

With BFS in mind, let’s take a look at this problem.

03, recursive solution

Again, let’s think about the recursive solution to this problem. When we think about recursion, we usually think about DFS first. We can perform a sequential traversal of the binary tree (root left and right order), record the level of the nodes, and define an array for each level, and then put the values of the nodes accessed into the array of the corresponding level.

Suppose the given binary tree is [3,9,20,null,null,15,7], the diagram is as follows:

Based on the above analysis, the code is as follows:

func levelOrder(root *TreeNode)[] []int {
    return dfs(root, 0And [] []int{})}func dfs(root *TreeNode, level int, res [][]int)[] []int {
	if root == nil {
		return res
	}
	if len(res) == level {
		res = append(res, []int{root.Val})
	} else {
		res[level] = append(res[level], root.Val)
	}
	res = dfs(root.Left, level+1, res)
	res = dfs(root.Right, level+1, res)
    return res
}
Copy the code

04, BFS solution

The above solution, in fact, is equivalent to using DFS method to achieve binary tree BFS. So can we use BFS directly to solve the problem? Of course, we can use the data structure of Queue. We initialize the root node into the queue and do BFS by consuming the tail and inserting the header.

The specific steps are shown below:

Based on the above analysis, the code is as follows:

func levelOrder(root *TreeNode)[] []int {
	var result [][]int
	if root == nil {
		return result
	}
    // Define a bidirectional queue
	queue := list.New()
    // Insert the header into the root node
	queue.PushFront(root)
    // Do a breadth search
	for queue.Len() > 0 {
		var current []int
		listLength := queue.Len()
		for i := 0; i < listLength; i++ {
		    // Consume tail
            // queue.remove (queue.back ()).(*TreeNode) : Removes the last element and converts it to type TreeNode
			node := queue.Remove(queue.Back()).(*TreeNode)
			current = append(current, node.Val)
			ifnode.Left ! =nil {
			    // Insert the header
				queue.PushFront(node.Left)
			}
			ifnode.Right ! =nil {
				queue.PushFront(node.Right)
			}
		}
		result = append(result, current)
	}
	return result
}
Copy the code

I’ve compiled all the problems I’ve written into an e-book, complete with illustrations for each problem. Click to download