按之字形顺序打印二叉树

题目描述

示例

示例1

输入：
{1,2,3,#,#,4,5}
返回值：
[[1],[3,2],[4,5]]
说明：
如题面解释，第一层是根节点，从左到右打印结果，第二层从右到左，第三层从左到右。

示例2

输入：
{8,6,10,5,7,9,11}
返回值：
[[8],[10,6],[5,7,9,11]]

示例3

输入：
{1,2,3,4,5}
返回值：
[[1],[3,2],[4,5]]

代码

代码1 层次遍历（使用队列辅助）

/*
使用层次遍历，
奇数层从左到右
偶数层从右到左
*/
function Print(pRoot)
{
    if(!pRoot) return []
    
    // 层次遍历，需要一个队列辅助，使用js的数组模拟
    let queue = []
    
    // 根节点入队
    queue.push(pRoot)
    
    let layer = 0 // 当前层数，默认为0
    
    let resultArr = [] // 最终输出的结果
    
    /*
    开始层次遍历
    1. 挨个遍历队列中当前层的节点，出队（先入先出原则）
    2. 依次把下一层的节点入队
    3. 循环1，2
    */ 
    while(queue.length > 0) {
        // 获取当前队列的长度（当前层的总结点数）
        let size = queue.length
        
        let thisLayerArr = [] // 当前层输出的结果
        
        // 开始遍历本层节点
        while(size!==0){
            // 出队（先入先出）
            let currentNode = queue.shift()
            
            // 入队下一层的节点
            if(currentNode.left){
                queue.push(currentNode.left)
            }
            if(currentNode.right){
                queue.push(currentNode.right)
            }
            
            // 如果当前层为偶数 0 2 4，因为这里layer默认为0，所以0的时候从左向右输出
            if(layer%2==0){
                thisLayerArr.push(currentNode.val)
            }else { // 为奇数层 1 3 5
                thisLayerArr.unshift(currentNode.val)
            }
            
            
            // 本层节点数减一，当size为0时，表示该层遍历完毕
            size--
        }
        
        // 每次遍历一层后 layer++
        layer++
        
        // 把本层的结果保存到最终结果数组中
        resultArr.push(thisLayerArr)
    }
    
    return resultArr
    
}

时间复杂度O(n)：n为遍历的节点总数

空间复杂度O(n)：队列占用的空间

题目来源

JZ77 按之字形顺序打印二叉树