【树遍历】树广度遍历以及记录节点层级

之前遇到过一道面试题，解法是利用队列来进行树的广度优先遍历，但是怎么记录每个节点的层数，被卡住了。
参考了下其他人的思路，关键在于每层遍历结束的时候，添加一个特殊标记表示层数出队结束了。
-请试着写一个JS算法为下面的节点树testNode的层级level赋值，如根节点level = 0，一级节点level = 1， 以此类推。

• typescript版本

//2. 请试着写一个JS算法为下面的节点树testNode的层级level赋值，如根节点level = 0，一级节点level = 1， 以此内推。
export interface Node {
    name: string;
    level: number;
    nodes: Array<Node>;
}

// 提示：可以用数组的队列特性，shift & push 方法。
function getNodesLevel(node: Node) {
    let nodes = [];
    // TODO
    let queue:Array<Node|null> = [];
    let i = 1;
    if(node!=null){
//跟节点入队，并给层级数赋值1
        node.level = i;
        queue.push(node);
//null标记入队，如果null出队了，说明同层已经全部出队了
        queue.push(null);
//1层只有一个，所以接下来的node都是2层以上了
        i++;
        while(queue.length != 0){
//队列头元素先出队
            let current = queue.shift();
            if(current !== null && current !== undefined){
//当前出队元素如果有下级子节点，让它的下级子节点继续入队
//因为当前node和它兄弟node肯定比它的子节点早入队
//所以可以保证先输出同层的兄弟节点
                let children = current.nodes;
                for(let j=0;j<children.length;j++){
                    children[j].level = i;
                    queue.push(children[j]);
                }
            } else if(current === null){
//如果null标记出队了，说明一层的元素都遍历过了，层级标记可以++了
//元素出队的时候queue为空，加入null的话会导致死循环
                if(queue.length != 0){
                  queue.push(null);
                }
                i++;
            }
            nodes.push(current);
        }
    }
    return nodes;
}

let testNode: Node = {
    name: 'test node',
    level: 0,
    nodes: [
        {
            name: 'node 1', level: 0, nodes: [
                {
                    name: 'node 1-1', level: 0, nodes: [
                        {
                            name: 'node 1-1-1', level: 0, nodes: []
                        },
                        {
                            name: 'node 1-1-2', level: 0, nodes: []
                        }
                    ]
                },
                { name: 'node 1-2', level: 0, nodes: [] }
            ]
        },
        {
            name: 'node 2', level: 0, nodes: [
                { name: 'node 2-1', level: 0, nodes: [] }
            ]
        },
        {
            name: 'node 3', level: 0, nodes: []
        }
    ]
}

getNodesLevel(testNode);
console.log(testNode);

• js版本

function getNodesLevel(node) {
    let nodes = [];
    // TODO
    let queue = [];
    let i = 1;
    if (node != null) {
        node.level = i;
        queue.push(node);
        queue.push(null);
        i++;
        while (queue.length != 0) {
            let current = queue.shift();
            if (current !== null && current !== undefined) {
                let children = current.nodes;
                for (let j = 0; j < children.length; j++) {
                    children[j].level = i;
                    queue.push(children[j]);
                }
            }
            else if (current === null) {
                if (queue.length != 0) {
                    queue.push(null);
                }
                i++;
            }
            nodes.push(current);
        }
    }
    return nodes;
}

二叉树层次遍历如何判断当前结点是哪层的？
js中的广度优先遍历（BFS）和深度优先遍历（DFS）