Cabbage Java self study room covers core knowledge

Force buckles the original problem

102. Sequence traversal of binary trees

Given a binary tree, 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
[[3], [9,20], [15,7]Copy the code

DFS (Depth-first Search) and BFS (breadth-first search)

DFS (depth-first search) and BFS (breadth-first search) are like twins, one always comes to mind with the other. If we use DFS/BFS just to traverse all the nodes of a tree or graph, then DFS and BFS are no different in power, and we prefer DFS traversal that is easier to write and less complex in space.

Let’s first look at the code comparison between DFS traversal and BFS traversal on a binary tree.

DFS traversal uses recursion:

void dfs(TreeNode root) {
    if (root == null) {
        return;
    }
    dfs(root.left);
    dfs(root.right);
}
Copy the code

BFS traversal uses queue data structures:

void bfs(TreeNode root) { Queue<TreeNode> queue = new ArrayDeque<>(); queue.add(root); while (! queue.isEmpty()) { TreeNode node = queue.poll(); if (node.left ! = null) { queue.add(node.left); } if (node.right ! = null) { queue.add(node.right); }}}Copy the code

Just comparing two pieces of code, the most intuitive feeling is: DFS traversal code is much simpler than BFS! This is because the recursive approach implicitly uses the stack of the system and we do not need to maintain a data structure ourselves. If you simply walk through the binary tree, then DFS is obviously the more convenient choice.

Although DFS and BFS traverse all nodes of binary tree once, they traverse nodes in different order.

Their thinking

What is sequential traversal? Simply put, sequential traversal means layering a binary tree and traversing each layer from left to right:

At first glance, this traversal order is the same as BFS, we can directly use BFS to obtain the sequence traversal results. However, sequence traversal requires different input results than BFS. Sequential traversal requires us to differentiate each layer, which returns a two-dimensional array. The BFS traversal results in a one-dimensional array that does not distinguish between each layer.

So, how do you layer the results of BFS traversal? Capture a moment in the BFS traversal:

As you can see, the nodes in the queue are 3, 4, and 5 from layer 1 and layer 2 respectively. At this point, the nodes of tier 1 come in before the nodes of tier 2 go out, and the nodes of tier 2 are next to each other in the queue, so we can’t tell which tier the nodes in the queue come from. Therefore, we need to modify the code slightly to record the number of nodes in the queue NNN (i.e. the number of nodes in this layer) before each layer is traversed, and then process the number of nodes in this layer in one go

In this way, we transform BFS traversal into sequential traversal. In the traversal process, the process of node entering and leaving the queue is as follows:

As you can see, in each round of the while loop, all nodes of the current layer are dequeued, and all nodes of the next layer are queued, thus realizing the sequence traversal.

Code implementation

public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); Queue<TreeNode> queue = new ArrayDeque<>(); if (root ! = null) { queue.add(root); } while (! queue.isEmpty()) { int n = queue.size(); List<Integer> level = new ArrayList<>(); for (int i = 0; i < n; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left ! = null) { queue.add(node.left); } if (node.right ! = null) { queue.add(node.right); } } res.add(level); } return res; }Copy the code

Complexity analysis

  • Time complexity: Each point enters and exits the queue once, so the progressive time complexity is O(n)O(n)O(n).

  • Space complexity: The number of elements in the queue does not exceed NNN, so the progressive space complexity is O(n)O(n)O(n).