特别说明
这一期和下一期视频，会讲解二叉树高频题目，但是不含树型 dp 的题目
- 树型 dp 问题，会放在【必备】课程的动态规划大章节部分讲述
- 树型 dp 中的换根 dp 问题，会放在【扩展】课程的动态规划大章节部分讲述
- AVL 树的实现，树的左旋、右旋，这些内容也会在【扩展】课程里讲述
题目1.二叉树的层序遍历
题目描述
给你二叉树的根节点 root ，返回其节点值的 层序遍历 （即逐层地，从左到右访问所有节点）
测试链接
思路
借助 队列，一次处理二叉树的一层
答案
题目2.二叉树的锯齿形层序遍历
题目描述
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 （即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）
测试链接
思路
和 上题 一样的套路
答案
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func zigzagLevelOrder(root *TreeNode) [][]int {
ans := [][]int{}
queue := []*TreeNode{}
reverse := false
if root != nil {
queue = append(queue, root)
}
for len(queue) > 0 {
size := len(queue)
curAns := make([]int, size)
for i := 0; i < size; i++ {
cur := queue[i]
if !reverse {
curAns[i] = cur.Val
} else {
curAns[size-1-i] = cur.Val
}
if cur.Left != nil {
queue = append(queue, cur.Left)
}
if cur.Right != nil {
queue = append(queue, cur.Right)
}
}
ans = append(ans, curAns)
reverse = !reverse
queue = queue[size:]
}
return ans
}题目3.二叉树的最大特殊宽度
题目描述
给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
题目数据保证答案将会在 32 位 带符号整数范围内。
测试链接
思路
和 上题 一样的套路 + 一个小技巧：记录每个节点在二叉树的编号（数组表示完全二叉树）
答案
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type nodeInfo struct {
*TreeNode
position int // 位置，根节点：0；左子节点：i<<1+1；右节点：i<<1+2
}
func widthOfBinaryTree(root *TreeNode) int {
ans := 0
queue := []nodeInfo{}
if root != nil {
queue = append(queue, nodeInfo{root, 0})
}
for len(queue) > 0 {
size := len(queue)
ans = max(ans, queue[size-1].position-queue[0].position+1)
for i := 0; i < size; i++ {
cur := queue[i]
if cur.Left != nil {
queue = append(queue, nodeInfo{cur.Left, cur.position<<1 + 1})
}
if cur.Right != nil {
queue = append(queue, nodeInfo{cur.Right, cur.position<<1 + 2})
}
}
queue = queue[size:]
}
return ans
}题目4.求二叉树的最大深度、求二叉树的最小深度
测试链接
思路
两种解法：
- 上题 套路（广度优先）
- 递归
答案
题目5.二叉树先序序列化和反序列化
题目描述
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
测试链接 ^1
思路
先序遍历，nil 节点用“#”占位
答案
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type Codec struct {
strings.Builder
}
func Constructor() Codec {
return Codec{}
}
// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
this.Reset()
var preOrder func(root *TreeNode)
preOrder = func(root *TreeNode) {
if root == nil {
this.WriteString(",#")
return
}
fmt.Fprintf(this, ",%d", root.Val)
preOrder(root.Left)
preOrder(root.Right)
}
preOrder(root)
return this.String()[1:]
}
// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
arr := strings.Split(data, ",")
idx := 0
var generate func() *TreeNode
generate = func() *TreeNode {
cur := arr[idx]
idx++
if cur == "#" {
return nil
}
val, _ := strconv.Atoi(cur)
node := &TreeNode{
Val: val,
}
node.Left = generate()
node.Right = generate()
return node
}
return generate()
}
/**
* Your Codec object will be instantiated and called as such:
* ser := Constructor();
* deser := Constructor();
* data := ser.serialize(root);
* ans := deser.deserialize(data);
*/题目6.二叉树按层序列化和反序列化
测试链接
答案
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type Codec struct {
strings.Builder
}
func Constructor() Codec {
return Codec{}
}
// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
this.Reset()
queue := []*TreeNode{}
// 加入队列时，序列化
if root != nil {
queue = append(queue, root)
fmt.Fprintf(this, ",%d", root.Val)
} else {
this.WriteString(",#")
}
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; i++ {
cur := queue[i]
if cur.Left != nil {
queue = append(queue, cur.Left)
fmt.Fprintf(this, ",%d", cur.Left.Val)
} else {
this.WriteString(",#")
}
if cur.Right != nil {
queue = append(queue, cur.Right)
fmt.Fprintf(this, ",%d", cur.Right.Val)
} else {
this.WriteString(",#")
}
}
queue = queue[size:]
}
return this.String()[1:]
}
// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
arr := strings.Split(data, ",")
idx := 0
var generate = func() *TreeNode {
cur := arr[idx]
idx++
if cur == "#" {
return nil
}
val, _ := strconv.Atoi(cur)
return &TreeNode{
Val: val,
}
}
root := generate()
if root == nil {
return root
}
queue := []*TreeNode{root}
for len(queue) > 0 {
cur := queue[0]
cur.Left = generate()
cur.Right = generate()
if cur.Left != nil {
queue = append(queue, cur.Left)
}
if cur.Right != nil {
queue = append(queue, cur.Right)
}
queue = queue[1:]
}
return root
}
/**
* Your Codec object will be instantiated and called as such:
* ser := Constructor();
* deser := Constructor();
* data := ser.serialize(root);
* ans := deser.deserialize(data);
*/总结
二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化
但是，二叉树无法通过中序遍历的方式实现序列化和反序列化
因为不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样，如：
__2 1__
/ 和 \
1 2补足空位置的中序遍历结果都是 [nil, 1, nil, 2, nil]
题目7.利用先序与中序遍历序列构造二叉树
测试链接
答案
总结
前中后序中，知道中序和另外一个序即可构建出一颗唯一的二叉树，只知道前序和后序而不知道中序则无法构建出唯一的二叉树
题目8.验证完全二叉树
题目描述
给你一棵二叉树的根节点 root ，请你判断这棵树是否是一棵 完全二叉树 。
在一棵完全二叉树中，除了最后一层外，所有层都被完全填满，并且最后一层中的所有节点都尽可能靠左。
最后一层（第 h 层）中可以包含 1 到 2h 个节点。
测试链接
思路
层序遍历（广度优先），有两种情况不是完全二叉树：
- 一个节点有右子树，而无左子树
- 遍历过子节点不全的节点后，又遍历到非叶子节点（有子节点）
答案
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isCompleteTree(root *TreeNode) bool {
queue := []*TreeNode{}
// 是否遇到过左右两个孩子不双全的节点
leaf := false
if root != nil {
queue = append(queue, root)
}
for len(queue) > 0 {
cur := queue[0]
if cur.Left == nil && cur.Right != nil {
// 情况一：一个节点有右子树，而无左子树
return false
}
if leaf && (cur.Left != nil || cur.Right != nil) {
// 情况二：遍历过子节点不全的节点后，又遍历到非叶子节点
return false
}
if cur.Left != nil {
queue = append(queue, cur.Left)
}
if cur.Right != nil {
queue = append(queue, cur.Right)
}
if cur.Left == nil || cur.Right == nil {
leaf = true
}
queue = queue[1:]
}
return true
}题目9.求完全二叉树的节点个数
要求时间复杂度低于 O(n)