首页 > 试题广场 >

从下到上打印二叉树

[编程题]从下到上打印二叉树
  • 热度指数:1869 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一棵二叉树,返回齐自底向上的层序遍历。

数据范围:二叉树上节点数满足 ,二叉树上的值满足

样例图:

示例1

输入

{1,2,3,4,#,5,6}

输出

[[4,5,6],[2,3],[1]]

说明

如题面图示 
示例2

输入

{1,2}

输出

[[2],[1]]

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
package main
import _"fmt"
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型二维数组
*/
func levelOrderBottom( root *TreeNode ) [][]int {
    ans:=[][]int{[]int{root.Val}}
    q:=[]*TreeNode{root}
    for len(q)>0{
        new_q:=[]*TreeNode{}
        vals:=[]int{}
        for _,qi:=range q{
            if qi.Left!=nil{
                new_q=append(new_q,qi.Left)
                vals=append(vals,qi.Left.Val)
            }
            if qi.Right!=nil{
                new_q=append(new_q,qi.Right)
                vals=append(vals,qi.Right.Val)
            }
        }
        if len(vals)>0{
            ans=append([][]int{vals},ans...)
        }
        q=new_q
    }
    return ans
}

发表于 2023-03-07 23:47:06 回复(0)
先层序遍历,再翻转数组即可
func levelOrderBottom( root *TreeNode ) (result [][]int) {
    var dfs func(*TreeNode, int)
    dfs = func(node *TreeNode, level int) {
        if node == nil {return}
        if len(result) == level {
            result = append(result, []int{})
        }
        result[level] = append(result[level], node.Val)
        dfs(node.Left, level+1)
        dfs(node.Right, level+1)
    }
    dfs(root, 0)
    //翻转数组
    for l, r := 0, len(result)-1; l < r; {
        result[l], result[r] = result[r], result[l]
        l++; r--
    }
    return
}


发表于 2021-11-26 16:07:07 回复(0)