二叉树的层序遍历

标签:地址   img   evel   width   data   左右   概念   roo   mamicode   

题目描述:

给你一个二叉树,请你返回其按 层序遍历 得到的节点值。(即逐层地,从左到右访问所有节点)。

示例:二叉树:[3,9,20,null,null,15,7],

    3
/ \
9 20
/ \
15 7

返回其层次遍历结果:

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

  

解题思路:

首先我们要知道层序遍历考查的其实就是广度优先遍历(BFS),聪明的朋友肯定还知道他的孪生兄弟深度优先遍历(DFS),篇幅较长这里就不过多介绍,感兴趣的朋友请自行了解。

要想完成广度优先遍历,我们要借助队列(先进先出,后进后出)的概念。

思想 :当队列中的队首出队的时候,要从二叉搜索树中找到它的两个孩子入队。队列出队为空的时候,就将二叉树遍历完成了。

我们再归纳一下广度优先遍历的步骤:

1、将根节点入队(入队的时候不做别的操作);

2、队列非空,所以接下来就要出队,规则是:依次出队,只要出队的元素有孩子,左右孩子依次入队,如果没有孩子不做任何操作。

另外,由于此题的返回数据格式是封装每层,所以这里可以定义一个count计录每层的数量

用简便图解如下:

技术图片

 

//go 
//* Definition for a binary tree node.
type TreeNode struct {
 Val int
 Left *TreeNode
 Right *TreeNode
}

func levelOrder(root *TreeNode) [][]int {
 var res [][]int
 if root == nil {
  return res
 }
 queue := make([]*TreeNode,0)
 queue = append(queue, root) // 添加到队尾,等于add()
 for len(queue) != 0 {
  count := len(queue)
  var list []int
  for count > 0 {
   node := queue[0] //取出队首,等于poll()
   queue = queue[1:] //移出队首更新队列
   list = append(list, node.Val)
   if node.Left != nil {
    queue = append(queue, node.Left)
   }
   if node.Right != nil {
    queue = append(queue, node.Right)
   }
   count--
  }
  res = append(res, list)
 }
 return res
}

  地址:https://mp.weixin.qq.com/s/Gb9bg04PMR4mwM2ZET8HnA

 

二叉树的层序遍历

标签:地址   img   evel   width   data   左右   概念   roo   mamicode   

原文地址:https://www.cnblogs.com/smallleiit/p/13488672.html

版权声明:完美者 发表于 2020-08-12 15:48:20。
转载请注明:二叉树的层序遍历 | 完美导航

暂无评论

暂无评论...