Ahri-珊

day29将分享二叉树的层次遍历。

方法1

时间复杂度n*n

缺点：时间复杂度高

优点：能记录每一层的节点

代码：

var levelOrderBottom = function(root) {
    // 遍历树的每一层

    for(let i=1;;i++)
        {
            // 找到层数为i的节点输出，找不到跳出循环

            if(!printLevel(root,i))
                break;
        }
};
// 输出层数为level的节点

var printLevel = function(root,level)
{
    // level<1说明当前层数节点已经完全输出此时结束递归

    if(!root||level<1)
        return false;
    // level=1说明这个节点是我要找这的这一层的节点

    if(level==1)
        console.log(root.val);
    // 一直往下一层找，直到level<1

    printLevel(root.left,level-1);  
    printLevel(root.right,level-1);  
    return true;
}

方法2

时间复杂度n

缺点：不知道每一层有哪些节点

优点：时间复杂度低

代码：

function walkTree(root) {
    var arr = [];
    while(root)
    {
        console.log(root.val);
        if (root.left) arr.push(root.left);
        if (root.right) arr.push(root.right);
        root = arr.shift();
    }
}

方法3

方法2的递归实现

时间复杂度n

缺点：不知道每一层有哪些节点

优点：时间复杂度低

代码：

var arr = [];
function walkTree(root) {
    // root为空时遍历完成结束递归

    if(!root)
        return ;
    console.log(root.val);
    if (root.left) 
        arr.push(root.left);
    if (root.right) 
        arr.push(root.right);
    return walkTree(arr.shift());
}

方法4

结合方法1、2，既能找出每一层的节点，时间复杂度又低，为了方便测试，我直接改成了LeetCode上层次遍历的解法。

要求： Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its bottom-up level order traversal as: [ [15,7], [9,20], [3] ]

代码：

var levelOrderBottom = function(root) {
    // 初始化数组存储层次遍历结果

    var arr = new Array();
    return printlevel(root,0,arr).reverse();
};
// 将每一层的节点作为一个数组存入arr

var printLevel = function(root,level,arr)
{
    // root为空时递归结束

    if(root)
    {
        // 将当前节点放入对应所在层数对应的数组

        if(!arr[level])
            arr[level] = [];
        arr[level].push(root.val);
        // 将子节点放入对应所在层数对应的数组

        level ++;
        if(root.left) 
            printLevel(root.left,level,arr);
        if(root.right) 
            printLevel(root.right,level,arr);
    }
    return arr;
}

END