从下到上打印二叉树

[编程题]从下到上打印二叉树

热度指数：1869 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵二叉树，返回齐自底向上的层序遍历。

数据范围：二叉树上节点数满足 $1 \le n \le 1000 \$ ，二叉树上的值满足 $|val| \le 10^9 \$

样例图：

示例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)

王飞-6

先层序遍历，再翻转数组即可

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)