从上到下打印二叉树

  • 时间:
  • 浏览:
  • 来源:互联网

题目描述

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回:

[3,9,20,15,7]

提示:

节点总数 <= 1000

解题思路

构建两个数组,一个是正常的空数组,作为返回的结果。另一个是树节点数字,存放读取到的左右根节点数据。
如果根节点为空,那么什么也不做,直接返回空数组。
如果不为空,读取树的根节点的值,然后存储读取到的不为空子节点。
最后进入循环,如果树节点数组不为空,说明一直有数据,然后进行节点的值的获取和根节点数据的读取,这样就是广度优先遍历。
注意输入一个节点,但是不存在走右节点的情况

提交结果

在这里插入图片描述

package main

import "fmt"

func main() {
    head := new(TreeNode)
    head.Val = 1
    list2 := new(TreeNode)
    list2.Val = 2
    head.Left = list2
    list3 := new(TreeNode)
    list3.Val = 3
    head.Right = list3
    list4 := new(TreeNode)
    list4.Val = 4
    list2.Left = list4
    fmt.Println(levelOrder(head))
}
func levelOrder(root *TreeNode) []int {
    var a []int
    var b []TreeNode
    if root == nil {
    } else {
        if root.Left!=nil{
            b = append(b, *root.Left)
        }
        if root.Right!=nil{
            b = append(b, *root.Right)
        }
        a = append(a, root.Val)
        for len(b) != 0 {
            a = append(a, b[0].Val)

            if b[0].Left != nil {
                b = append(b, *b[0].Left)
            }
            if b[0].Right != nil {
                b = append(b, *b[0].Right)
            }
            b = b[1:]
        }
    }
    return a
}

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

本文链接http://www.dzjqx.cn/news/show-617240.html