二叉树的广度优先遍历

需求

给定一颗二叉树，返回它的广度优先遍历(层次遍历)

我们只需要先按照层次遍历创建一颗二叉树，然后遍历将其复原即可

实现

let arr = ['a', 'b', 'c', 'd', '#', '#', 'e', '#', 'f', '#', '#', '#', '#']; //给定的序列
function TreeNode(val){
    this.val = val;
    this.left = null;
    this.right = null;
}
function createTree_levelorder(arr){
    let rootval = arr.shift();
    let queue = [];
    if(rootval){
        let root = new TreeNode(rootval);  //创建根节点
        queue.push(root);
        while(queue.length){
            let node = queue.shift();  //返回头结点
            let leftval = arr.shift();  //
            let rightval = arr.shift();
            if(leftval!=='#'){
                let leftnode = new TreeNode(leftval);
                queue.push(leftnode);
                node.left = leftnode;
            }
            if(rightval!=='#'){
                let rightnode = new TreeNode(rightval);
                queue.push(rightnode);
                node.right = rightnode;
            }
        }
        return root;
    }
}
function bfs(root){
    let res = [];
    let queue = [];
    if(root){
        queue.push(root);
        res.push(root.val);
        while(queue.length){
            let node = queue.shift()
            if(node.left){
                queue.push(node.left);
                res.push(node.left.val);
            }else{
                res.push('#');  //如果是叶子节点
            }
            if(node.right){
                queue.push(node.right);
                res.push(node.right.val);
            }else{
                res.push('#');
            }
        }
    }
    return res;
}
let root = createTree_levelorder(arr);
console.log(bfs(root));
//'a', 'b', 'c', 'd', '#', '#', 'e', '#', 'f', '#', '#', '#', '#'
//与形成时的序列相同