“I haven’t practiced for so long that I’m out of practice

The knowledge point used is obviously BFS, may have talked about the sequence traversal in class, but I have forgotten all, consolidate the foundation, too vegetables.

Method 1: BFS iteration

A binary tree can be iterated by placing the root node in a secondary queue and iterating through the queue.

Steps:

  1. First of all, it makes a special determination whether it’s an empty tree.
  2. Then create an answer array, a secondary queue, and put the root node into the secondary queue
  3. The queue is traversed until the queue is empty
  4. Pop up the head node of the queue and save its value in an auxiliary array that distinguishes the data between layers
  5. Check whether the left and right children of this node exist, and if so, pop them to the end of the queue
  6. Repeat steps 4 and 5
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number[][]}* /
var levelOrder = function (root) {
    if(! root)return []
    let res = []
    let queue = [root]
    while (queue.length) {  // Traverse until the secondary queue is empty
        let len = queue.length
        let level_res = []
        for (let i = 0; i < len; i++) {
            let temp = queue.shift()   // Pop the secondary queue header and save it
            if (temp.left) queue.push(temp.left)  // Check whether the left and right children exist
            if (temp.right) queue.push(temp.right)
            level_res.push(temp.val)
        }
        res.push(level_res)
    }
    return res
};
Copy the code

Method two: DFS recursion

Traversing the binary tree in order with an index tag, each time dividing the binary tree data by index.

var levelOrder = function (root) {
    if(! root)return [] // Special judgment
    let res=[[]]   // Specifically reserve an array layer for the root node
    DFS(root,res,0)  / / DFS entrance
    return res
};

var DFS = function(node,res,index){
    if(! node)return    // If the node is empty, return
    if(res.length<=index) res.push([])    // Insert a layer of array ahead of time to avoid "of null"
    res[index].push(node.val)   // Start the sequential traversal and insert the corresponding number of layers
    DFS(node.left,res,index+1)  // left subtree traversal
    DFS(node.right,res,index+1) // right subtree traversal
}
Copy the code

The code for DFS obviously feels cleaner, because DFS implicitly calls a stack structure that doesn’t need to be maintained by itself.

It’s all order N in time.