目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
二叉树层级遍历
访问量:1892
一、简介
给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
二叉树:[3,9,20,null,null,15,7]
3 / \ 9 20 / \ 15 7
返回其层次遍历结果:[3,9,20,15,7]
go语言 二叉树结构 如下:
type TreeNode struct { Val int Left *TreeNode Right *TreeNode }
二、解决方案
2.1、利用队列
a.构建简单的队列,先进先出
type Queue struct { data []*TreeNode } func (q *Queue) Push(n *TreeNode) { if q.data == nil { q.data = make([]*TreeNode, 0) } q.data = append(q.data, n) } func (q *Queue) Pop() *TreeNode { if len(q.data) == 0 { return nil } node := q.data[0] q.data = q.data[1:] return node }
b.利用队列层次遍历二叉树
func levelOrder(root *TreeNode) []int { rs := make([]int, 0) q := new(Queue) q.Push(root) for { curNode := q.Pop() if curNode == nil { break } rs = append(rs, curNode.Val) if curNode.Left != nil { q.Push(curNode.Left) } if curNode.Right != nil { q.Push(curNode.Right) } } return rs }
c.测试
func main() { head := &TreeNode{ Val:3, Left:&TreeNode{ Val:9, }, Right:&TreeNode{ Val:20, Left:&TreeNode{ Val:15, }, Right:&TreeNode{ Val:7, }, }, } data := levelOrder(head) fmt.Println(data) }
三、层次遍历变种1
输出如下结构:
[ [3], [9,20], [15,7] ]
相当于每层封装到一个数组里面,代码实现如下:
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ type Queue struct { data []*TreeNode } func (q *Queue) Push(n *TreeNode) { if q.data == nil { q.data = make([]*TreeNode, 0) } q.data = append(q.data, n) } func (q *Queue) Pop() *TreeNode { if len(q.data) == 0 { return nil } node := q.data[0] q.data = q.data[1:] return node } func (q *Queue)Len()int { return len(q.data) } func levelOrder(root *TreeNode) [][]int { if root == nil { return nil } q := new(Queue) q.Push(root) rs := make([][]int, 0) for q.Len() > 0 { // 当前层的个数为 count := q.Len() curData := make([]int, 0) // 保存当前层级的元素 // 取出当前层的节点,并将下一层节点插入队列 for i:=0; i< count; i++ { curNode := q.Pop() if curNode.Left != nil { q.Push(curNode.Left) } if curNode.Right != nil { q.Push(curNode.Right) } curData = append(curData, curNode.Val) } rs = append(rs, curData) } return rs }
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助