从上往下打印二叉树

题目描述

示例

代码

代码1 层次遍历 输出结果

/*
层次遍历
使用个队列辅助
*/
function PrintFromTopToBottom(root)
{
    if(!root) return []
    
    let q = [] // 使用数组模拟队列
    q.push(root) // 入队
    
    let result = []
    
    // 开始层次遍历
    while(q.length>0){
        let current = q.shift() // shift模拟出队
        
        // 挨个把本层的val塞到数组中
        result.push(current.val)
        
        // 把下一次的节点入队
        if(current.left){
            q.push(current.left)
        }
        if(current.right){
            q.push(current.right)
        }
    }
    
    return result
    
}

时间复杂度 O(N) ： N为二叉树的节点数量，层次遍历需循环N次。 空间复杂度 O(N) ： 最差情况下，当树为平衡二叉树时，最多有N/2个树节点同时在队列/栈中，使用O(N)大小的额外空间。

题目来源

JZ32 从上往下打印二叉树