首页 > 其他 > 详细

剑指 Offer 32 - II. 从上到下打印二叉树 II

时间:2021-05-21 14:28:40      阅读:15      评论:0      收藏:0      [点我收藏+]

剑指 Offer 32 - II. 从上到下打印二叉树 II

从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。

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

    3
   /   9  20
    /     15   7

返回其层次遍历结果:

[
  [3],
  [9,20],
  [15,7]
]

提示:

  1. 节点总数 <= 1000

注意:本题与主站 102 题相同:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

思路

golang

采用广度优先遍历BFS,在层序遍历的基础上 将每一层的节点的值保存在一个数组中,最后结果保存在二维数组中。
引入一个queue队列保存遍历的节点,然后依次取出每个节点,将节点的值加入每一层的结果集中,再判断该节点的左右孩子是否不为nil,如果不为nil则再加入queue队列,然后更新队列,将当前节点出队。最后将这一层的结果追加到最终的二维结果集中。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
/*
在层序遍历的基础上 将每一层的节点的值保存在一个数组中,最后结果保存在二维数组中
引入一个queue队列保存遍历的节点,然后从节点队列中深入获取值
*/
func levelOrder(root *TreeNode) [][]int {
	// 新建一个保存节点值得队列
	var queue []*TreeNode
	// 新建一个用于保存最终结果的值
	var result [][]int

	if root != nil {
		queue = append(queue, root)
	}

	// 开始从节点队列中进行遍历
	for len(queue) != 0 {
		// 新建一个数组保存每一层的节点值
		var res []int
		// 获取
		size := len(queue)
		for i := 0; i < size; i++ {
			node := queue[0]
			res = append(res, node.Val)
			// 排除已经遍历的节点
			queue = queue[1:]

			// 向队列中添加子节点
			if node.Left != nil {
				queue = append(queue, node.Left)
			}

			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
		// 向最终结果集中添加每一层的节点值
		result = append(result, res)
	}

	return result
}

剑指 Offer 32 - II. 从上到下打印二叉树 II

原文:https://www.cnblogs.com/zmk-c/p/14793258.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!