二叉树的创建(层次遍历)

需求

根据二叉树的层次遍历的序列结果，创建二叉树

eg:[‘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);  //队列中存的是节点才能找到left，right
        while(queue.length){
            let head = queue.shift(); //队列头节点出队
            let left = arr.shift();//左节点的值
            let right = arr.shift();  //右节点的值
            if(left!=='#'){ //左节点值不为空
                let leftnode = new TreeNode(left); //新建节点
                queue.push(leftnode);
                head.left = leftnode;
            }
            if(right!=='#'){
                let rightnode = new TreeNode(right);
                queue.push(rightnode);
                head.right = rightnode;
            }
        }     
        return root;
    }
}
let arr = ['a','b','c','d','#','#','e','#','f','#','#','#','#'];
console.log(createTree_levelorder(arr));
//值得注意的是，在left和right那里并没有判断是否为空
//因为层次遍历到最后两个一定为"#",所以并不会加入到队列中，等到队列为空自然退出循环