LeetCode 102 on the sequential traversal stack of binary trees

Topic:

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

Returns the result of its hierarchical traversal:

[[3], [9,20], [15,7]Copy the code

Idea 1:

From the title “sequence traversal”, it is easy to think of the breadth-first traversal of binary trees. They want the value of the binary tree to be returned by level, so we can traverse with depth as the node. Iterate one layer at a time, storing the sons of that layer in the array for the next iteration. Until the array is empty. The code is as follows:

var levelOrder = function(root) {
    if(! root)return [];
    let arr = [],list = [root];
    while(list.length>0) {let currentArr=[],childArr=[];
        for(let node of list){
            if(! node)continue;
            currentArr.push(node.val);
            childArr.push(node.left);
            childArr.push(node.right);
        }
        if(currentArr.length>0) arr.push(currentArr);
        list = childArr;
    }
    return arr;
};
Copy the code

Idea 2:

This problem can also be solved by depth-first traversal. Each time the depth level is entered, the value is stored in the array according to the different level. The code is as follows:

var levelOrder = function(root) {
    let arr=[],level=0;
    function levelSearch(root,level){
        if(root==null) return;
        if(arr[level]){
            arr[level].push(root.val);
        }else{
            arr[level] = [root.val];
        }
        levelSearch(root.left,level+1);
        levelSearch(root.right,level+1);
    }    
    levelSearch(root,level);
    return arr;
};
Copy the code

I’m doing it recursively, or I can do it by pushing each node on the stack. I’m not going to do the demo here.