二叉树

知识点

二叉树遍历

前序遍历先访问根节点,再前序遍历左子树,再前序遍历右子树 中序遍历:先中序遍历左子树,再访问根节点,再中序遍历右子树 后序遍历:先后序遍历左子树,再后序遍历右子树,再访问根节点
注意点
  • 以根访问顺序决定是什么遍历
  • 左子树都是优先右子树

前序递归

1
func preorderTraversal(root *TreeNode) {
2
if root==nil{
3
return
4
}
5
// 先访问根再访问左右
6
fmt.Println(root.Val)
7
preorderTraversal(root.Left)
8
preorderTraversal(root.Right)
9
}
Copied!

前序非递归

1
// V3:通过非递归遍历
2
func preorderTraversal(root *TreeNode) []int {
3
// 非递归
4
if root == nil{
5
return nil
6
}
7
result:=make([]int,0)
8
stack:=make([]*TreeNode,0)
9
10
for root!=nil || len(stack)!=0{
11
for root !=nil{
12
// 前序遍历,所以先保存结果
13
result=append(result,root.Val)
14
stack=append(stack,root)
15
root=root.Left
16
}
17
// pop
18
node:=stack[len(stack)-1]
19
stack=stack[:len(stack)-1]
20
root=node.Right
21
}
22
return result
23
}
Copied!

中序非递归

1
// 思路:通过stack 保存已经访问的元素,用于原路返回
2
func inorderTraversal(root *TreeNode) []int {
3
result := make([]int, 0)
4
if root == nil {
5
return result
6
}
7
stack := make([]*TreeNode, 0)
8
for len(stack) > 0 || root != nil {
9
for root != nil {
10
stack = append(stack, root)
11
root = root.Left // 一直向左
12
}
13
// 弹出
14
val := stack[len(stack)-1]
15
stack = stack[:len(stack)-1]
16
result = append(result, val.Val)
17
root = val.Right
18
}
19
return result
20
}
Copied!

后序非递归

1
func postorderTraversal(root *TreeNode) []int {
2
// 通过lastVisit标识右子节点是否已经弹出
3
if root == nil {
4
return nil
5
}
6
result := make([]int, 0)
7
stack := make([]*TreeNode, 0)
8
var lastVisit *TreeNode
9
for root != nil || len(stack) != 0 {
10
for root != nil {
11
stack = append(stack, root)
12
root = root.Left
13
}
14
// 这里先看看,先不弹出
15
node:= stack[len(stack)-1]
16
// 根节点必须在右节点弹出之后,再弹出
17
if node.Right == nil || node.Right == lastVisit {
18
stack = stack[:len(stack)-1] // pop
19
result = append(result, node.Val)
20
// 标记当前这个节点已经弹出过
21
lastVisit = node
22
} else {
23
root = node.Right
24
}
25
}
26
return result
27
}
Copied!
注意点
  • 核心就是:根节点必须在右节点弹出之后,再弹出

DFS 深度搜索-从上到下

1
type TreeNode struct {
2
Val int
3
Left *TreeNode
4
Right *TreeNode
5
}
6
7
func preorderTraversal(root *TreeNode) []int {
8
result := make([]int, 0)
9
dfs(root, &result)
10
return result
11
}
12
13
// V1:深度遍历,结果指针作为参数传入到函数内部
14
func dfs(root *TreeNode, result *[]int) {
15
if root == nil {
16
return
17
}
18
*result = append(*result, root.Val)
19
dfs(root.Left, result)
20
dfs(root.Right, result)
21
}
Copied!

DFS 深度搜索-从下向上(分治法)

1
// V2:通过分治法遍历
2
func preorderTraversal(root *TreeNode) []int {
3
result := divideAndConquer(root)
4
return result
5
}
6
func divideAndConquer(root *TreeNode) []int {
7
result := make([]int, 0)
8
// 返回条件(null & leaf)
9
if root == nil {
10
return result
11
}
12
// 分治(Divide)
13
left := divideAndConquer(root.Left)
14
right := divideAndConquer(root.Right)
15
// 合并结果(Conquer)
16
result = append(result, root.Val)
17
result = append(result, left...)
18
result = append(result, right...)
19
return result
20
}
Copied!
注意点:
DFS 深度搜索(从上到下) 和分治法区别:前者一般将最终结果通过指针参数传入,后者一般递归返回结果最后合并

BFS 层次遍历

1
func levelOrder(root *TreeNode) [][]int {
2
// 通过上一层的长度确定下一层的元素
3
result := make([][]int, 0)
4
if root == nil {
5
return result
6
}
7
queue := make([]*TreeNode, 0)
8
queue = append(queue, root)
9
for len(queue) > 0 {
10
list := make([]int, 0)
11
// 为什么要取length?
12
// 记录当前层有多少元素(遍历当前层,再添加下一层)
13
l := len(queue)
14
for i := 0; i < l; i++ {
15
// 出队列
16
level := queue[0]
17
queue = queue[1:]
18
list = append(list, level.Val)
19
if level.Left != nil {
20
queue = append(queue, level.Left)
21
}
22
if level.Right != nil {
23
queue = append(queue, level.Right)
24
}
25
}
26
result = append(result, list)
27
}
28
return result
29
}
Copied!

分治法应用

先分别处理局部,再合并结果
适用场景
  • 快速排序
  • 归并排序
  • 二叉树相关问题
分治法模板
  • 递归返回条件
  • 分段处理
  • 合并结果
1
func traversal(root *TreeNode) ResultType {
2
// nil or leaf
3
if root == nil {
4
// do something and return
5
}
6
7
// Divide
8
ResultType left = traversal(root.Left)
9
ResultType right = traversal(root.Right)
10
11
// Conquer
12
ResultType result = Merge from left and right
13
14
return result
15
}
Copied!

典型示例

1
// V2:通过分治法遍历二叉树
2
func preorderTraversal(root *TreeNode) []int {
3
result := divideAndConquer(root)
4
return result
5
}
6
func divideAndConquer(root *TreeNode) []int {
7
result := make([]int, 0)
8
// 返回条件(null & leaf)
9
if root == nil {
10
return result
11
}
12
// 分治(Divide)
13
left := divideAndConquer(root.Left)
14
right := divideAndConquer(root.Right)
15
// 合并结果(Conquer)
16
result = append(result, root.Val)
17
result = append(result, left...)
18
result = append(result, right...)
19
return result
20
}
Copied!

归并排序

1
func MergeSort(nums []int) []int {
2
return mergeSort(nums)
3
}
4
func mergeSort(nums []int) []int {
5
if len(nums) <= 1 {
6
return nums
7
}
8
// 分治法:divide 分为两段
9
mid := len(nums) / 2
10
left := mergeSort(nums[:mid])
11
right := mergeSort(nums[mid:])
12
// 合并两段数据
13
result := merge(left, right)
14
return result
15
}
16
func merge(left, right []int) (result []int) {
17
// 两边数组合并游标
18
l := 0
19
r := 0
20
// 注意不能越界
21
for l < len(left) && r < len(right) {
22
// 谁小合并谁
23
if left[l] > right[r] {
24
result = append(result, right[r])
25
r++
26
} else {
27
result = append(result, left[l])
28
l++
29
}
30
}
31
// 剩余部分合并
32
result = append(result, left[l:]...)
33
result = append(result, right[r:]...)
34
return
35
}
Copied!
注意点
递归需要返回结果用于合并

快速排序

1
func QuickSort(nums []int) []int {
2
// 思路:把一个数组分为左右两段,左段小于右段,类似分治法没有合并过程
3
quickSort(nums, 0, len(nums)-1)
4
return nums
5
6
}
7
// 原地交换,所以传入交换索引
8
func quickSort(nums []int, start, end int) {
9
if start < end {
10
// 分治法:divide
11
pivot := partition(nums, start, end)
12
quickSort(nums, 0, pivot-1)
13
quickSort(nums, pivot+1, end)
14
}
15
}
16
// 分区
17
func partition(nums []int, start, end int) int {
18
p := nums[end]
19
i := start
20
for j := start; j < end; j++ {
21
if nums[j] < p {
22
swap(nums, i, j)
23
i++
24
}
25
}
26
// 把中间的值换为用于比较的基准值
27
swap(nums, i, end)
28
return i
29
}
30
func swap(nums []int, i, j int) {
31
t := nums[i]
32
nums[i] = nums[j]
33
nums[j] = t
34
}
Copied!
注意点:
快排由于是原地交换所以没有合并过程 传入的索引是存在的索引(如:0、length-1 等),越界可能导致崩溃
常见题目示例

maximum-depth-of-binary-tree

给定一个二叉树,找出其最大深度。
思路:分治法
1
func maxDepth(root *TreeNode) int {
2
// 返回条件处理
3
if root == nil {
4
return 0
5
}
6
// divide:分左右子树分别计算
7
left := maxDepth(root.Left)
8
right := maxDepth(root.Right)
9
10
// conquer:合并左右子树结果
11
if left > right {
12
return left + 1
13
}
14
return right + 1
15
}
Copied!

balanced-binary-tree

给定一个二叉树,判断它是否是高度平衡的二叉树。
思路:分治法,左边平衡 && 右边平衡 && 左右两边高度 <= 1, 因为需要返回是否平衡及高度,要么返回两个数据,要么合并两个数据, 所以用-1 表示不平衡,>0 表示树高度(二义性:一个变量有两种含义)。
1
func isBalanced(root *TreeNode) bool {
2
if maxDepth(root) == -1 {
3
return false
4
}
5
return true
6
}
7
func maxDepth(root *TreeNode) int {
8
// check
9
if root == nil {
10
return 0
11
}
12
left := maxDepth(root.Left)
13
right := maxDepth(root.Right)
14
15
// 为什么返回-1呢?(变量具有二义性)
16
if left == -1 || right == -1 || left-right > 1 || right-left > 1 {
17
return -1
18
}
19
if left > right {
20
return left + 1
21
}
22
return right + 1
23
}
Copied!
注意
一般工程中,结果通过两个变量来返回,不建议用一个变量表示两种含义

binary-tree-maximum-path-sum

给定一个非空二叉树,返回其最大路径和。
思路:分治法,分为三种情况:左子树最大路径和最大,右子树最大路径和最大,左右子树最大加根节点最大,需要保存两个变量:一个保存子树最大路径和,一个保存左右加根节点和,然后比较这个两个变量选择最大值即可
1
type ResultType struct {
2
SinglePath int // 保存单边最大值
3
MaxPath int // 保存最大值(单边或者两个单边+根的值)
4
}
5
func maxPathSum(root *TreeNode) int {
6
result := helper(root)
7
return result.MaxPath
8
}
9
func helper(root *TreeNode) ResultType {
10
// check
11
if root == nil {
12
return ResultType{
13
SinglePath: 0,
14
MaxPath: -(1 << 31),
15
}
16
}
17
// Divide
18
left := helper(root.Left)
19
right := helper(root.Right)
20
21
// Conquer
22
result := ResultType{}
23
// 求单边最大值
24
if left.SinglePath > right.SinglePath {
25
result.SinglePath = max(left.SinglePath + root.Val, 0)
26
} else {
27
result.SinglePath = max(right.SinglePath + root.Val, 0)
28
}
29
// 求两边加根最大值
30
maxPath := max(right.MaxPath, left.MaxPath)
31
result.MaxPath = max(maxPath,left.SinglePath+right.SinglePath+root.Val)
32
return result
33
}
34
func max(a,b int) int {
35
if a > b {
36
return a
37
}
38
return b
39
}
Copied!

lowest-common-ancestor-of-a-binary-tree

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
思路:分治法,有左子树的公共祖先或者有右子树的公共祖先,就返回子树的祖先,否则返回根节点
1
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
2
// check
3
if root == nil {
4
return root
5
}
6
// 相等 直接返回root节点即可
7
if root == p || root == q {
8
return root
9
}
10
// Divide
11
left := lowestCommonAncestor(root.Left, p, q)
12
right := lowestCommonAncestor(root.Right, p, q)
13
14
15
// Conquer
16
// 左右两边都不为空,则根节点为祖先
17
if left != nil && right != nil {
18
return root
19
}
20
if left != nil {
21
return left
22
}
23
if right != nil {
24
return right
25
}
26
return nil
27
}
Copied!

BFS 层次应用

binary-tree-level-order-traversal

给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)
思路:用一个队列记录一层的元素,然后扫描这一层元素添加下一层元素到队列(一个数进去出来一次,所以复杂度 O(logN))
1
func levelOrder(root *TreeNode) [][]int {
2
result := make([][]int, 0)
3
if root == nil {
4
return result
5
}
6
queue := make([]*TreeNode, 0)
7
queue = append(queue, root)
8
for len(queue) > 0 {
9
list := make([]int, 0)
10
// 为什么要取length?
11
// 记录当前层有多少元素(遍历当前层,再添加下一层)
12
l := len(queue)
13
for i := 0; i < l; i++ {
14
// 出队列
15
level := queue[0]
16
queue = queue[1:]
17
list = append(list, level.Val)
18
if level.Left != nil {
19
queue = append(queue, level.Left)
20
}
21
if level.Right != nil {
22
queue = append(queue, level.Right)
23
}
24
}
25
result = append(result, list)
26
}
27
return result
28
}
Copied!

binary-tree-level-order-traversal-ii

给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
思路:在层级遍历的基础上,翻转一下结果即可
1
func levelOrderBottom(root *TreeNode) [][]int {
2
result := levelOrder(root)
3
// 翻转结果
4
reverse(result)
5
return result
6
}
7
func reverse(nums [][]int) {
8
for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 {
9
nums[i], nums[j] = nums[j], nums[i]
10
}
11
}
12
func levelOrder(root *TreeNode) [][]int {
13
result := make([][]int, 0)
14
if root == nil {
15
return result
16
}
17
queue := make([]*TreeNode, 0)
18
queue = append(queue, root)
19
for len(queue) > 0 {
20
list := make([]int, 0)
21
// 为什么要取length?
22
// 记录当前层有多少元素(遍历当前层,再添加下一层)
23
l := len(queue)
24
for i := 0; i < l; i++ {
25
// 出队列
26
level := queue[0]
27
queue = queue[1:]
28
list = append(list, level.Val)
29
if level.Left != nil {
30
queue = append(queue, level.Left)
31
}
32
if level.Right != nil {
33
queue = append(queue, level.Right)
34
}
35
}
36
result = append(result, list)
37
}
38
return result
39
}
Copied!

binary-tree-zigzag-level-order-traversal

给定一个二叉树,返回其节点值的锯齿形层次遍历。Z 字形遍历
1
func zigzagLevelOrder(root *TreeNode) [][]int {
2
result := make([][]int, 0)
3
if root == nil {
4
return result
5
}
6
queue := make([]*TreeNode, 0)
7
queue = append(queue, root)
8
toggle := false
9
for len(queue) > 0 {
10
list := make([]int, 0)
11
// 记录当前层有多少元素(遍历当前层,再添加下一层)
12
l := len(queue)
13
for i := 0; i < l; i++ {
14
// 出队列
15
level := queue[0]
16
queue = queue[1:]
17
list = append(list, level.Val)
18
if level.Left != nil {
19
queue = append(queue, level.Left)
20
}
21
if level.Right != nil {
22
queue = append(queue, level.Right)
23
}
24
}
25
if toggle {
26
reverse(list)
27
}
28
result = append(result, list)
29
toggle = !toggle
30
}
31
return result
32
}
33
func reverse(nums []int) {
34
for i := 0; i < len(nums)/2; i++ {
35
nums[i], nums[len(nums)-1-i] = nums[len(nums)-1-i], nums[i]
36
}
37
}
Copied!

二叉搜索树应用

validate-binary-search-tree

给定一个二叉树,判断其是否是一个有效的二叉搜索树。
思路 1:中序遍历,检查结果列表是否已经有序
思路 2:分治法,判断左 MAX < 根 < 右 MIN
1
// v1
2
func isValidBST(root *TreeNode) bool {
3
result := make([]int, 0)
4
inOrder(root, &result)
5
// check order
6
for i := 0; i < len(result) - 1; i++{
7
if result[i] >= result[i+1] {
8
return false
9
}
10
}
11
return true
12
}
13
14
func inOrder(root *TreeNode, result *[]int) {
15
if root == nil{
16
return
17
}
18
inOrder(root.Left, result)
19
*result = append(*result, root.Val)
20
inOrder(root.Right, result)
21
}
Copied!
1
// v2分治法
2
type ResultType struct {
3
IsValid bool
4
// 记录左右两边最大最小值,和根节点进行比较
5
Max *TreeNode
6
Min *TreeNode
7
}
8
9
func isValidBST2(root *TreeNode) bool {
10
result := helper(root)
11
return result.IsValid
12
}
13
func helper(root *TreeNode) ResultType {
14
result := ResultType{}
15
// check
16
if root == nil {
17
result.IsValid = true
18
return result
19
}
20
21
left := helper(root.Left)
22
right := helper(root.Right)
23
24
if !left.IsValid || !right.IsValid {
25
result.IsValid = false
26
return result
27
}
28
if left.Max != nil && left.Max.Val >= root.Val {
29
result.IsValid = false
30
return result
31
}
32
if right.Min != nil && right.Min.Val <= root.Val {
33
result.IsValid = false
34
return result
35
}
36
37
result.IsValid = true
38
// 如果左边还有更小的3,就用更小的节点,不用4
39
// 5
40
// / \
41
// 1 4
42
// / \
43
// 3 6
44
result.Min = root
45
if left.Min != nil {
46
result.Min = left.Min
47
}
48
result.Max = root
49
if right.Max != nil {
50
result.Max = right.Max
51
}
52
return result
53
}
Copied!

insert-into-a-binary-search-tree

给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。
思路:找到最后一个叶子节点满足插入条件即可
1
// DFS查找插入位置
2
func insertIntoBST(root *TreeNode, val int) *TreeNode {
3
if root == nil {
4
root = &TreeNode{Val: val}
5
return root
6
}
7
if root.Val > val {
8
root.Left = insertIntoBST(root.Left, val)
9
} else {
10
root.Right = insertIntoBST(root.Right, val)
11
}
12
return root
13
}
Copied!

总结

  • 掌握二叉树递归与非递归遍历
  • 理解 DFS 前序遍历与分治法
  • 理解 BFS 层次遍历

练习

最近更新 1yr ago