Binary tree sequence traversal: horizontal layer to output

In the figure, we output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Type according to Leetcode

[[1],
  [2.3],
  [4.5.6],
  [7.8.9.10]]Copy the code

It’s just a different way of getting the output

Iteration – Breadth first

The demo

Text parsing

  1. I’m going to push the first layer onto the stack
  2. The loop outputs each node in the stack one by one, and if there are children, the children are added to the next stack
  3. When all nodes in the current stack are printed, the next stack replaces the current stack
  4. Output is completed when there are no nodes in the current stack

code

function levelorder(root) {
    // The empty node case should not be forgotten 😭
    if(root === null) return []
    // Output the result
    const res = []
    // Push the first layer first
    let stack = [root]
    
    // Loop termination condition: there are no nodes in the stack
    while(stack.length) {
        // Loop through our nodes
        // Here we print the result as per LeetCode, one array per layer
        const level = []
        // We need the next layer of the stack to hold our next layer of nodes
        const nextLevelNodes = []
        for (let i = 0; i < stack.length; i++) {
            level.push(stack[i].val)
            if(stack[i].left) nextLevelNodes.push(stack[i].left)
            if(stack[i].right) nextLevelNodes.push(stack[i].right)
        }
        // output to our result
        res.push(level)
        // The output of the current layer is finished, we change the next layer to the current layer
        stack = nextLevelNodes
    }
    
    return res
}
Copy the code

Take a look at the official solution

The idea has been, the overall processing details are not quite the same

Recursion-depth first

The demo

Text parsing

  1. The result, res, is inserted into the traversed nodes by layer index
  2. Index + 1 traversal each time the child nodes are traversed, first to the leftmost node, and then once as shown

code

var levelOrder = function(root) {
    / / blank nodes
    if (root === null) return []
    // Define the output
    let res = []
    // Recursive traversal, pass the root node, layer number: start at layer 1, output result is saved
    dfs(root, 1, res)
    return res
};

function dfs(root, index, res) {
    // Add an empty array to the first depth traversal
    if (res.length < index) {
        res.push([])
    }
    // Then push val of the index-1 result of the index layer
    res[index - 1].push(root.val)
    // The number of levels traversed recursively by the child node is increased by 1
    if (root.left) dfs(root.left, index + 1, res)
    if (root.right) dfs(root.right, index + 1, res)
}
Copy the code

conclusion

  • Deep search, wide search application differentiation, flexible use of hierarchy index