二叉树及其相关题目 | Go 语言实现
二叉树是一种树状结构，每个节点都包含自身的数据，指向左子节点和右子节点的指针。
// 这是用链式存储的二叉树，也可以使用数组来存储，如 heap
type Node struct {
Data int
Left, Right *Node
}
遍历二叉树
二叉树根据遍历顺序的不同分了四种，分别是前序遍历，中序遍历，后序遍历和宽度优先遍历，前面三种遍历方式是深度优先遍历，根据头节点的位置区分的，最后一种遍历方式则是按层的方式从左往右遍历
递归方式：在递归遍历二叉树的时候，会先递归左子树，再递归右子树，再递归的过程中，每次会有三次到达自身的节点的机会，前中后序遍历就是在这三次不同的时机对自身节点进行操作。
前序
前序遍历的顺序是头左右
思路1：递归
// PreOrderTraversal 递归方式先序遍历二叉树
func PreOrderTraversal(head *Node) {
if head == nil {
return
}
fmt.Println(head.Data)
PreOrderTraversal(head.Left)
PreOrderTraversal(head.Right)
}
思路二：使用栈，先将 head 加入栈中，如果栈不为空，就执行以下操作
- head = stack.Pop() ，即栈弹出一个元素作为新 head
- 执行对 head 的操作，如打印
- 判断 head 的右子节点和左子节点是否为空，不是空就入栈，是空就不管，注意先操作右子节点再操作左子节点（这里如果先操作左节点再操作右节点最后的遍历序就会变成头右左，利用这一点可以实现后序遍历）
// PreOrderTraversal 使用栈的方式先序遍历二叉树
func PreOrderTraversal(head *Node) {
if head == nil {
return
}
stack := new(Stack)
stack.Push(head)
for !stack.IsEmpty() {
head = stack.Pop()
fmt.Println(head.Data)
if head.Right != nil {
stack.Push(head.Right)
}
if head.Left != nil {
stack.Push(head.Left)
}
}
}
中序
中序是左头右
思路1：递归
// InOrderTraversal 递归方式中序遍历二叉树
func InOrderTraversal(head *Node) {
if head != nil {
return
}
InOrderTraversal(head.Left)
fmt.Println(head.Data)
InOrderTraversal(head.Right)
}
思路二：使用栈，每颗子树，每棵子树左边界进栈，依次弹出节点的过程中处理弹出元素，对弹出节点的右树也重复此操作
// InOrderTraversal 使用栈的方式中序遍历二叉树
func InOrderTraversal(head *Node) {
if head == nil {
return
}
stack := new(Stack)
for !stack.IsEmpty() || head != nil {
if head != nil {
stack.Push(head)
head = head.Left
} else {
head = stack.Pop()
fmt.Println(head.Data)
head = head.Right
}
}
}
后序
后序是左右头
思路1：递归
// PosOrderTraversal 递归方式后序遍历二叉树
func PosOrderTraversal(head *Node) {
if head == nil {
return
}
PosOrderTraversal(head.Left)
PosOrderTraversal(head.Right)
fmt.Println(head.Data)
}
思路2：使用栈，在先序非递归遍历中，我们将每次对弹出的节点压入一个另一个新栈，入栈操作改成先压左节点再压右节点，最后再对新栈一直弹出就可以实现后序遍历
// PosOrderTraversal 使用栈的方式后序遍历二叉树
func PosOrderTraversal(head *Node) {
if head == nil {
return
}
stack1 := new(Stack)
stack2 := new(Stack)
stack1.Push(head)
for !stack1.IsEmpty() {
head = stack1.Pop()
stack2.Push(head)
if head.Left != nil {
stack1.Push(head.Left)
}
if head.Right != nil {
stack2.Push(head.Right)
}
}
for !stack2.IsEmpty() {
fmt.Println(stack2.Pop().Data)
}
}
宽度优先遍历
思路：使用队列，先将头节点放入队列，然后弹出，处理此元素，再将此元素的左节点和右节点放入队列（先左再右），循环此操作直到队列为空
// BSTraversal 宽度优先遍历
func BSTraversal(head *Node) {
if head == nil {
return
}
queue := new(Queue)
queue.Add(head)
for !queue.IsEmpty() {
cur := queue.Poll()
fmt.Println(cur.Data)
if cur.Left != nil {
queue.Add(cur.Left)
}
if cur.Right != nil {
queue.Add(cur.Right)
}
}
}
相关题目
求二叉树节点最多的层数和该层节点数
思路1：先使用一个 map 存储每个节点所在的层数，再使用变量记录下当前层数 curLevel，初始值为1，当前层的节点数 curLevelNodes，初始值为0，最多节点数 max，初始值为-1，max 所在的层数 maxLevel，初始值为1。在宽度优先遍历的基础上，每次对节点的处理改为：先获取此节点的层数与 curLevel 比较，如果相等就对 curLevelNodes++，如果不等说明此时已经来到了下一层，就对 curLevel++，对 max 和 maxLevel 进行一次更新，将 curLevelNodes 设置为1
每个节点的层数获取方法：在宽度优先遍历时，每次对当前处理节点的左节点和右节点进行入队列的同时，将其放入 map 中，层数就为当前节点所处层数+1
// GetMaxNodesAndLevel 获取二叉树节点最多的层数和该层的节点数
func GetMaxNodesAndLevel(head *Node) (int, int) {
if head == nil {
return 0, 0
}
queue := new(Queue)
queue.Add(head)
levelMap := make(map[*Node]int)
levelMap[head] = 1
curLevel, curLevelNodes, max, maxLevel := 1, 0, -1, 1
for !queue.IsEmpty() {
cur := queue.Poll()
if curLevel == levelMap[cur] {
curLevelNodes++
} else {
if max < curLevelNodes {
max = curLevelNodes
maxLevel = curLevel
}
curLevel++
curLevelNodes = 1
}
if cur.Left != nil {
queue.Add(cur.Left)
levelMap[cur.Left] = curLevel + 1
}
if cur.Right != nil {
queue.Add(cur.Right)
levelMap[cur.Right] = curLevel + 1
}
}
return max, maxLevel
}
思路2：使用 curEnd，nextEnd 分别记录当前层数的最后一个节点，和下一层数的最后一个节点，使用 curLevelNodes 和 max 记录当前层数的节点数和最大节点数，使用 maxLevel 和 curLevel 记录最大节点数所在的层数和当前的层数，一开始 curEnd 和 nextEnd 设置为 head 和 nil，curLevelNodes 和 max 都设置为0，maxLevel 和 curLevel 分别设置为0，1。在宽度优先遍历的基础上，将 nextEnd 设置为每次入队列的节点，每次弹出的节点与 curEnd 比较，如果不相等就 curLevelNodes++。如果相等就代表已经来到了这一层的最后一个节点，将 nextEnd 的值赋给 curEnd，nextEnd 赋值为 nil，curLevelNodes++，更新 max 和 maxLevel，将curLevelNodes再次设置为0，curLevel++。最终的 max 和 maxLevel 就是所给二叉树的最大节点数和其所在层数
// GetMaxNodesAndLevel 获取二叉树的节点最多的层数和该层的节点数
func GetMaxNodesAndLevel(head *Node) (int, int) {
if head == nil {
return 0, 0
}
queue := new(Queue)
queue.Add(head)
// cueEnd and nextEnd used to storage the last node in the current level and next level
var curEnd, nextEnd *Node = head, nil
max, maxLevel, curLevel, curLevelNodes := 0, 0, 1, 0
for !queue.IsEmpty() {
cur := queue.Poll()
if cur.Left != nil {
queue.Add(cur.Left)
nextEnd = cur.Left
}
if cur.Right != nil {
queue.Add(cur.Right)
nextEnd = cur.Right
}
// cur == curEnd means coming to the last node in the current level
if cur == curEnd {
// update curEnd and nextEnd
curEnd = nextEnd
nextEnd = nil
curLevelNodes++
if max < curLevelNodes {
// update max and maxLevel
max = curLevelNodes
maxLevel = curLevel
}
// reset the curLevelNodes to storage the next level's nodes num
curLevelNodes = 0
// update curLevel
curLevel++
} else {
curLevelNodes++
}
}
return max, maxLevel
}
判断二叉树是否是某种二叉树
判断一颗二叉树是否是搜索二叉树
二叉搜索树（Binary Search Tree）是一个有序树* 。
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树
思路1：递归
- head 的左右子树都是搜索二叉树
- head 大于左树上的最大值，小于右树上的最小值（这是判断一颗树是否为搜索二叉树的条件）
此时我们只需要左右树是否是搜索二叉树和左树上的最大值或有树上的最小值，但是递归每次返回信息应该是相同的，所以我们每次返回左树和右树是否为搜索二叉树，左树和右树各自的最大最小值
type ReturnData struct {
IsBST bool
Min, Max int
}
// IsBST 递归判断一颗二叉树是不是二叉搜索树
func IsBST(head *Node) bool {
return IsBSTProcess(head).IsBST
}
func IsBSTProcess(head *Node) *ReturnData {
if head == nil {
return nil
}
result := &ReturnData{IsBST: true, Max: head.Data, Min: head.Data}
leftData := IsBSTProcess(head.Left)
rightData := IsBSTProcess(head.Right)
// get current tree's max and min
if leftData != nil {
result.Min = int(math.Min(float64(leftData.Min), float64(head.Data)))
result.Max = int(math.Max(float64(leftData.Max), float64(head.Data)))
}
if rightData != nil {
result.Min = int(math.Min(float64(rightData.Min), float64(head.Data)))
result.Max = int(math.Max(float64(rightData.Max), float64(head.Data)))
}
// check whether current tree is a BST
if leftData != nil && (!leftData.IsBST || leftData.Max >= head.Data) {
result.IsBST = false
}
if rightData != nil && (!rightData.IsBST || rightData.Min <= head.Data) {
result.IsBST = false
}
return result
}
思路2：使用数组，中序遍历二叉树，每次将节点放入数组中，如果最后的数组不是有序的，根据最后数组是否有序判断是否为二叉搜索树
// IsBST 判断一颗树是不是二叉搜索树
func IsBST(head *Node) bool {
nodes := make([]*Node, 0)
process(head, nodes)
for i := 1; i < len(nodes); i++ {
if nodes[i].Data < nodes[i-1].Data {
return false
}
}
return true
}
func process(head *Node, nodes []*Node) {
if head == nil {
return
}
process(head.Left, nodes)
nodes = append(nodes, head)
process(head.Right, nodes)
}
判断一颗二叉树是完全二叉树
完全二叉树（complete binary tree） 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。
思路：对于一颗完全二叉树的每一个节点，如果他的右节点不为 nil，则他左节点也不为 nil，并且按照宽度优先遍历从第一个右节点为空的节点往后一定全部都是叶子节点，据此就可以判断一棵树是不是完全二叉树
// IsCBT 判断是否是一颗完全二叉树
func IsCBT(head *Node) bool {
if head == nil {
return true
}
queue := new(Queue)
queue.Add(head)
// leaf is set to true when the right child node is nil the first time it is encountered
leaf := false
for !queue.IsEmpty() {
cur := queue.Poll()
if (leaf && (cur.Left != nil || cur.Right != nil)) || (cur.Right != nil && cur.Left == nil) {
return false
}
if cur.Left != nil {
queue.Add(cur.Left)
}
if cur.Right != nil {
queue.Add(cur.Right)
} else {
leaf = true
}
}
return true
}
判断一颗二叉树是否是满二叉树
记节点个数为 nodes，层数为 l，那么一颗满二叉树一定满足：nodes = 2^l - 1（2的 l 次方减1），最后一层的节点数一定为 2^(l-1) （2的 l-1 次方）。
思路1：我们遍历二叉树的时候同时记录下层数和节点个数，如果满足上述条件，就返回 true，否则返回 false
// IsFBT 判断一颗二叉树是不是二叉树
func IsFBT(head *Node) bool {
if head == nil {
return false
}
queue := new(Queue)
queue.Add(head)
nodes, level := 0, 1
for !queue.IsEmpty() {
cur := queue.Poll()
nodes++
if cur.Left != nil {
queue.Add(cur.Left)
}
if cur.Right != nil {
queue.Add(cur.Right)
}
if cur.Left != nil || cur.Right != nil {
level++
}
}
if nodes != int(math.Pow(2, float64(level))) {
return false
}
return true
}
思路2：递归
- head 的左右子树都是满二叉树
- head 左右节点节点个数相等
// IsFBT 递归判断一颗树是不是满二叉树
func IsFBT(head *Node) bool {
ok, _ := FBTProcess(head)
return ok
}
func FBTProcess(head *Node) (bool, int) {
if head == nil {
return true, 0
}
leftOk, leftNum := FBTProcess(head.Left)
rightOk, rightNum := FBTProcess(head.Right)
if !leftOk || !rightOk || leftNum != rightNum {
return false, leftNum + rightNum + 1
}
return true, leftNum + rightNum + 1
}
判断一颗二叉树是否是平衡二叉树
平衡二叉树：一颗空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树
思路：递归
- head 的左右子树都是平衡二叉树
- head 的左右子树高度差不超过1
// IsBalanced 判断一颗二叉树是否是平衡二叉树
func IsBalanced(head *Node) bool {
ok, _ := IsBalancedProcess(head)
return ok
}
func IsBalancedProcess(head *Node) (bool, int) {
if head == nil {
return true, 0
}
leftOk, leftHeight := IsBalancedProcess(head.Left)
rightOk, RightHeight := IsBalancedProcess(head.Right)
if !leftOk || !rightOk || math.Abs(float64(leftHeight-RightHeight)) > 1 {
return false, int(math.Max(float64(leftHeight), float64(RightHeight))) + 1
}
return true, int(math.Max(float64(leftHeight), float64(RightHeight))) + 1
}
总结
树形DP：确定左树和右树需要提供的信息，分别从左数和右树得到信息后再组装自己所要提供出去的信息，返回给上一级（左树和右树提供的信息应该是一样的）
代码结构：1. 基本条件判断 2. 分别从左树和右树拿到信息 3. 组装自己的信息
最低公共祖先
给定一颗二叉树和当中的两个节点 node1，node2，找出这两个几点的最低公共节点
思路1：
- 从 head 的左右子树分别得到其是否含有 node1 或 node2 的信息
- 如果两边的返回都不为空代表当前节点为最低公共节点，否则返回不为空的子树提供的信息
// LowestCommonAncestor 找到最低公共祖先
func LowestCommonAncestor(head, node1, node2 *Node) *Node {
if head == nil || head == node1 || head == node2 {
return head
}
leftNode := LowestCommonAncestor(head.Left, node1, node2)
rightNode := LowestCommonAncestor(head.Right, node1, node2)
if leftNode != nil && rightNode != nil {
return head
}
if leftNode == nil {
return rightNode
}
return leftNode
}
思路2：利用 map，使用两个 map，一个记录每一个节点的父节点，记录完成后从 node1 开始往父节点方向走，每次走过的节点都放入第二个 map 中，直到走到头节点，然后从 node2 开始往父节点方向走，每次判断当前节点是否在第二个 map 中，第一次判断成功的节点就是最低公共祖先
// LowestCommonAncestor 使用 map，找到公共最低祖先
func LowestCommonAncestor(head, node1, node2 *Node) *Node {
fatherMap := make(map[*Node]*Node)
fatherSet := make(map[*Node]struct{})
LCAProcess(head, fatherMap)
cur := node1
fatherSet[cur] = struct{}{}
for cur != head {
fatherSet[fatherMap[cur]] = struct{}{}
cur = fatherMap[cur]
}
cur = node2
for cur != head {
_, ok := fatherSet[cur]
if ok {
return cur
}
cur = fatherMap[cur]
}
return head
}
func LCAProcess(head *Node, fatherMap map[*Node]*Node) {
if head.Left != nil {
fatherMap[head.Left] = head
LCAProcess(head.Left, fatherMap)
}
if head.Right != nil {
fatherMap[head.Right] = head
LCAProcess(head.Right, fatherMap)
}
}
后继节点
现在有一种新的二叉树节点类型如下:
type NewNode struct {
Data int
Parent, Left, Right *Node
}
该结构比普通二叉树节点结构多了一个指向父节点的 parent 指针。 假设有一棵 NewNode 类型的节点组成的二叉树，树中每个节点的 parent 指针都正确地指向自己的父节点，头节点的 parent 指向 nil。 只给一个在二叉树中的某个节点 node，请实现返回 node 的后继节点的函数。在二叉树的中序遍历的序列中， node 的下一个节点叫作 node 的后继节点。
思路1：暴力解题，先从 node 找到整棵树的 head，将二叉树进行中序遍历放入数组或者链表，再遍历数组或者链表找到 node 的后继节点
思路2：如果 node 的右子节点不为空，那后继节点就是右子节点作为头节点的子树的最左节点。右子节点为空，后继节点为在 node 父节点链上，第一个不是父节点右节点的节点的父节点（或者说是第一个是父节点的左节点的节点）。我们假设这个节点为 Y，那么 node 对于 Y 来说就是其左子树上的最右节点，所以 node 的后继节点一定是 Y
// GetSuccessorNode 在一个含有父节点指针的二叉树中获取 node 的后继节点
func GetSuccessorNode(node *NewNode) *NewNode {
if node == nil {
return node
}
if node.Right != nil {
// get the leftest node
head := node.Right
for head.Left != nil {
head = head.Left
}
return head
} else {
cur := node.Parent
for cur.Parent != nil && cur.Left != node {
cur = cur.Parent
node = node.Parent
}
return cur
}
}
二叉树的序列化和反序列化
将二叉树序列化为字符串，并根据得到的字符串能够反序列化
序列化思路：将按照一定的序列（先序，中序或后序），将每个节点的 data 按一定规则保存在字符串中，然后每个节点结尾拼接一个相同的字符，注意每个节点的子节点都要保存，如果是 nil，就用某一特殊符号表示，按序列将其拼接起来
// MarshalBTToString 将二叉树按先序序列化为一个字符串
func MarshalBTToString(head *Node) string {
return MProcess(head)
}
func MProcess(head *Node) string {
if head == nil {
return "*!"
}
leftRes := MProcess(head.Left)
rightRes := MProcess(head.Right)
return fmt.Sprintf("%d!%s%s", head.Data, leftRes, rightRes)
}
反序列化思路：在序列化时使用的什么顺序序列化再反序列化也要用相同的方式，上面使用的先序序列化，所以反序列化时要先建立左子树，再建立右子树
// UnMarshalStringToBT 将字符串反序列化到内存中的二叉树
func UnMarshalStringToBT(s string) *Node {
data := strings.Split(s, "!")
queue := new(StringQueue)
for i := 0; i < len(data)-1; i++ {
queue.Add(data[i])
}
return UProcess(queue)
}
func UProcess(queue *StringQueue) *Node {
value := queue.Poll()
if value == "!" {
return nil
}
data, err := strconv.ParseInt(value, 10, 64)
if err != nil {
return nil
}
node := &Node{Data: int(data)}
node.Left = UProcess(queue)
node.Right = UProcess(queue)
return node
}
折纸问题
请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。 此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。 给定一个输入参数N，代表纸条都从下边向上方连续对折N次。请从上到下打印所有折痕的方向。
例如:N=1时，打印: down N=2时，打印: down down up
思路：自己拿一张纸折，每次折后标记这是第几次折以及折痕的方向，会发现每次折纸都会在上一次的折痕上下分别出现凹折痕和凸折痕
，据此可以从第一条折痕为头构建一颗二叉树，最开始的头节点为凹折痕，每个节点的左子树头节点都为凹折痕，右子树头节点为凸折痕
最后中序遍历就是结果
// PaperFolds 解决折纸问题
func PaperFolds(n int) {
// true used to express 'down'
PaperFoldsProcess(n, true)
}
func PaperFoldsProcess(n int, b bool) {
if n < 1 {
return
}
PaperFoldsProcess(n-1, true)
if b {
fmt.Println("down")
} else {
fmt.Println("up")
}
PaperFoldsProcess(n-1, false)
}