把二叉树打印成多行

题目描述

示例

代码

代码1 层次遍历，一行一行的输出结果

/*
层次遍历，按行打印输出结果
使用一个队列辅助
使用一个临时数组用来存储本行的值
*/
function Print(pRoot)
{
    if(!pRoot) return []
    
    let q = [] // 使用数组模拟队列
    q.push(pRoot) // 入队
    
    let result = [] // 最终返回的结果
    
    // 开始层次遍历
    while(q.length > 0){ // 遍历本行节点
        
        let size = q.length // 本行一共有多少个节点
        
        let tempArr = [] // 用来存储本行节点的val，好存储到最终结果数组里
        
        // 开始遍历本行节点，同时把下一行节点重新入队
        while(size > 0){
            
            let current = q.shift() // 使用shift模拟出队
            
            // 将下一层节点重新入队
            if(current.left){
                q.push(current.left)
            }
            if(current.right){
                q.push(current.right)
            }
            
            tempArr.push(current.val) // 临时数组用来存储本行的节点的val
            
            size--
        }
        
        // 内层的while每次都是一行一行的来遍历，本行的结果都存储在了临时数组tempArr中
        // 将本行遍历的结果push到最终的结果数组中
        result.push(tempArr)
        
    }
    
    return result 
}

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

空间复杂度O(n)

题目来源

JZ78 把二叉树打印成多行