07-二叉树基本算法.md

[TOC]
# 1 二叉树基本算法

## 1.1 二叉树的遍历

### 1.1.1 二叉树节点定义

```Go
type Node struct {
	// 二叉树节点上的值
	Val int
	// 左孩子
	Left *Node
	// 右孩子
	Right *Node
}
```

### 1.1.2 递归实现先序中序后序遍历

> 先序：任何子树的处理顺序都是，先头结点，再左子树，再右子树。先处理头结点

> 中序：任何子树的处理顺序都是，先左子树，再头结点，再右子树。中间处理头结点

> 后序：任何子树的处理顺序都是，先左子树，再右子树，再头结点。最后处理头结点

对于下面的一棵树：

```
graph TD
1-->2
1-->3
2-->4
2-->5
3-->6
3-->7
```

1、 先序遍历为：1 2 4 5 3 6 7

2、 中序遍历为：4 2 5 1 6 3 7

3、 后序遍历为：4 5 2 6 7 3 1

```Go
package main

import "fmt"

type Node struct {
	// 二叉树节点上的值
	Val int
	// 左孩子
	Left *Node
	// 右孩子
	Right *Node
}

// Pre 给定二叉树头节点，先序遍历该二叉树
func (head *Node) Pre() {
	if head == nil {
		return
	}
	// 获取头节点，打印该头结点
	fmt.Println(head.Val)
	// 递归遍历左子树
	head.Left.Pre()
	// 递归遍历右子树
	head.Right.Pre()
}

// Mid 给定二叉树头节点，中序遍历该二叉树
func (head *Node) Mid() {
	if head == nil {
		return
	}
	// 递归遍历左子树
	head.Left.Mid()
	// 获取头节点，打印该头结点
	fmt.Println(head.Val)
	// 递归遍历右子树
	head.Right.Mid()
}

// Pos 给定二叉树头节点，后序遍历该二叉树
func (head *Node) Pos() {
	if head == nil {
		return
	}
	// 递归遍历左子树
	head.Left.Pos()
	// 递归遍历右子树
	head.Right.Pos()
	// 获取头节点，打印该头结点
	fmt.Println(head.Val)
}

func main() {
	head := &Node{Val: 1}
	head.Left = &Node{Val: 2}
	head.Right = &Node{Val: 3}
	head.Left.Left = &Node{Val: 4}
	head.Left.Right = &Node{Val: 5}
	head.Right.Left = &Node{Val: 6}
	head.Right.Right = &Node{Val: 7}
	
	head.Pre()
	fmt.Println("=========")
	head.Mid()
	fmt.Println("=========")
	head.Pos()
}
```

输出：

```shell
1
2
4
5
3
6
7
=========
4
2
5
1
6
3
7
=========
4
5
2
6
7
3
1

Process finished with the exit code 0

```

> 总结：对于树的递归，每个节点在递归的过程中实质上会到达三次，例如上文的树结构，我们在第一次到达当前节点就打印，对于以当前节点为树根的树，就是先序。同理，第二次到达当前节点就是中序，第三次到达该节点就是后序遍历。所以先序中序后序，只是我们的递归顺序加工出来的结果而已

### 1.1.3 非递归实现先序中序后序遍历(DFS)

思路：由于任何递归可以改为非递归，我们可以使用压栈来实现,实质就是深度优先遍历（DFS）。用先序实现的步骤，其他类似：

- 步骤一，把节点压入栈中，弹出就打印

- 步骤二，如果有右孩子先压入右孩子

- 步骤三，如果有左孩子压入左孩子

```Go
package main

import "fmt"

type Node struct {
	// 二叉树节点上的值
	Val int
	// 左孩子
	Left *Node
	// 右孩子
	Right *Node
}

// Pre 给定二叉树头节点，非递归先序遍历该二叉树
func (head *Node) Pre() {
	fmt.Println("pre-order: ")
	if head != nil {
		// 简单模拟一个栈
		stack := make([]*Node, 0)
		stack = append(stack, head)
		for len(stack) != 0 {
			// 出栈
			hd := stack[len(stack)-1]
			fmt.Println(hd.Val)
			stack = stack[:len(stack)-1]
			// 右孩子入栈
			if hd.Right != nil {
				stack = append(stack, hd.Right)
			}
			// 左孩子入栈
			if hd.Left != nil {
				stack = append(stack, hd.Left)
			}
		}
	}
	fmt.Println()
}

// Mid 给定二叉树头节点，非递归中序遍历该二叉树
func (head *Node) Mid() {
	fmt.Println("Mid-order:")
	if head != nil {
		hd := head
		// 简单模拟一个栈
		stack := make([]*Node, 0)
		for len(stack) != 0 || hd != nil {
			// 整条左边界依次入栈
			if hd != nil {
				stack = append(stack, hd)
				hd = hd.Left
			} else { // 左边界到头弹出一个打印，来到该节点右节点，再把该节点的左树以此进栈
				hd = stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				fmt.Println(hd.Val)
				hd = hd.Right
			}
		}
	}
	fmt.Println()
}

// Pos 给定二叉树头节点，非递归后序遍历该二叉树
func (head *Node) Pos() {
	fmt.Println("pos-order: ")
	if head != nil {
		hd := head
		// 借助两个辅助栈
		s1 := make([]*Node, 0)
		s2 := make([]*Node, 0)
		s1 = append(s1, hd)
		for len(s1) != 0 {
			// 出栈
			hd = s1[len(s1) - 1]
			s1 = s1[:len(s1) - 1]
			s2 = append(s2, hd)
			if hd.Left != nil {
				s1 = append(s1, hd.Left)
			}
			if hd.Right != nil {
				s1 = append(s1, hd.Right)
			}
		}
		for len(s2) != 0 {
			v := s2[len(s2) - 1]
			s2 = s2[:len(s2) - 1]
			fmt.Println(v.Val)
		}
	}
	fmt.Println()
}

func main() {
	head := &Node{Val: 1}
	head.Left = &Node{Val: 2}
	head.Right = &Node{Val: 3}
	head.Left.Left = &Node{Val: 4}
	head.Left.Right = &Node{Val: 5}
	head.Right.Left = &Node{Val: 6}
	head.Right.Right = &Node{Val: 7}

	head.Pre()
	fmt.Println("=========")
	head.Mid()
	fmt.Println("=========")
	head.Pos()
}
```

### 1.1.4 二叉树按层遍历(BFS)

1、 其实就是宽度优先遍历(BFS)，用队列

2、 可以通过设置flag变量的方式，来发现某一层的结束

> 按层打印输出二叉树

```GO
package main

import "fmt"

type Node struct {
	// 二叉树节点上的值
	Val int
	// 左孩子
	Left *Node
	// 右孩子
	Right *Node
}

// Level 按层遍历二叉树
func (head *Node) Level() {
	if head == nil {
		return
	}
	hd := head
	// 简单实现一个队列
	queue := make([]*Node, 0)
	// 加入头结点
	queue = append(queue, hd)
	// 队列不为空出队打印，把当前节点的左右孩子加入队列
	for len(queue) != 0 {
		// 弹出队列头部的元素
		cur := queue[0]
		queue = queue[1:]
		fmt.Println(cur.Val)
		if cur.Left != nil {
			queue = append(queue, cur.Left)
		}
		if cur.Right != nil {
			queue = append(queue, cur.Right)
		}
	}
}

func main() {
	head := &Node{Val: 1}
	head.Left = &Node{Val: 2}
	head.Right = &Node{Val: 3}
	head.Left.Left = &Node{Val: 4}
	head.Left.Right = &Node{Val: 5}
	head.Right.Left = &Node{Val: 6}
	head.Right.Right = &Node{Val: 7}

	head.Level()
}
```

> 找到二叉树的最大宽度

```Go
package main

import "math"

type Node struct {
	// 二叉树节点上的值
	Val int
	// 左孩子
	Left *Node
	// 右孩子
	Right *Node
}

// MaxWidthUseMap 给定二叉树头节点，找到该二叉树的最大宽度，借助map结构实现
func (head *Node) MaxWidthUseMap() int {
	if head == nil {
		return 0
	}
	hd := head
	queue := make([]*Node, 0)
	queue = append(queue, hd)

	// map的Key:节点 map的value:节点属于哪一层
	levelMap := make(map[*Node]int, 0)
	// 头节点head属于第一层
	levelMap[hd] = 1
	// 当前正在统计那一层的宽度
	curLevel := 1
	// 当前curLevel层，宽度目前是多少
	curLevelNodes := 0
	// 用来保存所有层的最大宽度的值
	max := 0
	for len(queue) != 0 {
		cur := queue[0]
		queue = queue[1:]
		curNodeLevel := levelMap[cur]
		// 当前节点的左孩子不为空，队列加入左孩子，层数在之前层上加1
		if cur.Left != nil {
			levelMap[cur.Left] = curNodeLevel + 1
			queue = append(queue, cur.Left)
		}
		// 当前节点的右孩子不为空，队列加入右孩子，层数也变为当前节点的层数加1
		if cur.Right != nil {
			levelMap[cur.Right] = curNodeLevel + 1
			queue = append(queue, cur.Right)
		}
		// 当前层等于正在统计的层数，不结算
		if curNodeLevel == curLevel {
			curLevelNodes ++
		} else {
			// 新的一层，需要结算
			// 得到目前为止的最大宽度
			max = int(math.Max(float64(max), float64(curLevelNodes)))
			curLevel++
			// 结算后，当前层节点数设置为1
			curLevelNodes = 1
		}
	}
	// 由于最后一层，没有新的一层去结算，所以这里单独结算最后一层
	max = int(math.Max(float64(max), float64(curLevelNodes)))
	return max
}

// MaxWidthNoMap 给定二叉树头节点，找到该二叉树的最大宽度，不借助map实现
func (head *Node) MaxWidthNoMap() int {
	if head == nil {
		return 0
	}

	hd := head
	queue := make([]*Node, 0)
	queue = append(queue, hd)

	// 当前层，最右节点是谁，初始head的就是本身
	curEnd := head
	// 如果有下一层，下一层最右节点是谁
	var nextEnd *Node = nil
	// 全局最大宽度
	max := 0
	// 当前层的节点数
	curLevelNodes := 0
	for len(queue) != 0 {
		cur := queue[0]
		queue = queue[1:]
		// 左边不等于空，加入左
		if cur.Left != nil {
			queue = append(queue, cur.Left)
			// 孩子的最右节点暂时为左节点
			nextEnd = cur.Left
		}
		// 右边不等于空，加入右
		if cur.Right != nil {
			queue = append(queue, cur.Right)
			// 如果有右节点，孩子层的最右要更新为右节点
			nextEnd = cur.Right
		}
		// 由于最开始弹出当前节点，那么该层的节点数加一
		curLevelNodes++
		// 当前节点是当前层最右的节点，进行结算
		if cur == curEnd {
			// 当前层的节点和max进行比较，计算当前最大的max
			max = int(math.Max(float64(max), float64(curLevelNodes)))
			// 即将进入下一层，重置下一层节点为0个节点
			curLevelNodes = 0
			// 当前层的最右，直接更新为找出来的下一层最右
			curEnd = nextEnd
		}
	}
	return max
}
```

## 1.2 二叉树的序列化和反序列化

1、 可以用先序或者中序或者后序或者按层遍历，来实现二叉树的序列化

2、 用了什么方式的序列化，就用什么方式的反序列化。后续序列化和按层序列化略，感兴趣可以自己查资料


> 由于如果树上的节点值相同，那么序列化看不出来该树的结构，所以我们的序列化要加上空间结构的标识，空节点补全的方式。

```Go
package main

import "strconv"

type Node struct {
	// 二叉树节点上的值
	Val int
	// 左孩子
	Left *Node
	// 右孩子
	Right *Node
}

// PreSerial 二叉树的先序列化
func (head *Node) PreSerial() []string {
	// 简单实现一个队列
	ans := make([]string, 0)
	// 先序的序列化结果依次放入队列中去
	pres(head, ans)
	return ans
}

func pres(head *Node, ans []string) {
	if head == nil {
		ans = append(ans, "")
	} else {
		ans = append(ans, strconv.Itoa(head.Val))
		pres(head.Left, ans)
		pres(head.Right, ans)
	}
}

// BuildByPreQueue 根据先序序列化的结果，重新构建该二叉树。反序列化
func BuildByPreQueue(preQueue []string) *Node {
	if len(preQueue) == 0 {
		return nil
	}

	return preb(preQueue)
}

func preb(preQueue []string) *Node {
	v := preQueue[0]
	preQueue = preQueue[1:]

	// 如果头节点是空的话，返回空
	if v == "" {
		return nil
	}

	// 否则根据第一个值构建先序的头结点
	if iv, err := strconv.Atoi(v); err == nil {
		head := &Node{Val: iv}
		// 递归建立左树
		head.Left = preb(preQueue)
		// 递归建立右树
		head.Right = preb(preQueue)
		return head
	}
	return nil
}
```

## 1.3 题目实战

### 1.3.1 题目一：返回二叉树的后继节点

题目描述：二叉树的结构定义如下：

```Go
type Node struct {
	// 二叉树节点上的值
	Val int
	// 左孩子
	Left *Node
	// 右孩子
	Right *Node
	// 指向父亲的指针
	Parent *Node
}
```

给你二叉树中的某个节点，返回该节点的后继节点。后继节点表示一颗二叉树中，在**中序遍历**的序列中，一个节点的下一个节点是哪个。

> 方法一，通常解法思路：由于我们的节点有指向父节点的指针，而整颗二叉树的头结点的父节点为null。那么我们可以找到整棵树的头结点，然后中序遍历，再找到给定节点的下一个节点，就是该节点的后续节点。


> 方法二，考虑一个节点和其后继节点的结构之间的关系：

> 如果一个节点x有右树，那么其后继节点就是右树最左的节点。

> 如果x没有右树，往上找父亲节点。如果x是其父亲的右孩子继续往上找，如果某节点是其父亲节点的左孩子，那么该节点的父亲就是x的后继节点

> 即如果某节点左树的最右节点是x，那么该节点是x的后继

> 如果找父节点，一直找到null都不满足，那么该节点是整棵树的最右节点，没有后继

```Go
package main

import "fmt"

type Node struct {
	// 二叉树节点上的值
	Val int
	// 左孩子
	Left *Node
	// 右孩子
	Right *Node
	// 指向父亲的指针
	Parent *Node
}

// GetSuccessorNode 给定二叉树的一个节点node，返回该节点的后继节点
func GetSuccessorNode(node *Node) *Node {
	if node == nil {
		return  node
	}

	if node.Right != nil {
		return getLeftMost(node.Right)
	} else { // 无右子树
		parent := node.Parent
		// 当前节点是其父亲节点右孩子，继续
		for parent != nil && parent.Right == node {
			node = parent
			parent = node.Parent
		}
		return parent
	}
}

// 找右树上的最左节点
func getLeftMost(node *Node) *Node {
	if node == nil {
		return node
	}
	for node.Left != nil {
		node = node.Left
	}
	return node
}

func main() {
	head := &Node{Val: 6}
	head.Parent = nil
	head.Left = &Node{Val: 3}
	head.Left.Parent = head
	head.Left.Left = &Node{Val: 1}
	head.Left.Left.Parent = head.Left
	head.Left.Left.Right = &Node{Val: 2}
	head.Left.Left.Right.Parent = head.Left.Left
	head.Left.Right = &Node{Val: 4}
	head.Left.Right.Parent = head.Left
	head.Left.Right.Right = &Node{Val: 5}
	head.Left.Right.Right.Parent = head.Left.Right
	head.Right = &Node{Val: 9}
	head.Right.Parent = head
	head.Right.Left = &Node{Val: 8}
	head.Right.Left.Parent = head.Right
	head.Right.Left.Left = &Node{Val: 7}
	head.Right.Left.Left.Parent = head.Right.Left
	head.Right.Right = &Node{Val: 10}
	head.Right.Right.Parent = head.Right


	test := head.Left.Left
	fmt.Println(fmt.Sprintf("节点：%d的后继节点为%d", test.Val, GetSuccessorNode(test).Val))

	test = head.Left.Left.Right
	fmt.Println(fmt.Sprintf("节点：%d的后继节点为%d", test.Val, GetSuccessorNode(test).Val))

	test = head.Left.Right.Left
	fmt.Println(fmt.Sprintf("节点：%d的后继节点为%d", test.Val, GetSuccessorNode(test).Val))
	
	test = head
	fmt.Println(fmt.Sprintf("节点：%d的后继节点为%d", test.Val, GetSuccessorNode(test).Val))
	
	test = head.Right.Left.Left
	fmt.Println(fmt.Sprintf("节点：%d的后继节点为%d", test.Val, GetSuccessorNode(test).Val))
}
```

> 后继节点对应的是前驱结点，前驱结点的含义是中序遍历，某节点的前一个节点