二叉树及其相关题目 | 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 加入栈中，如果栈不为空，就执行以下操作

 // 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：递归

此时我们只需要左右树是否是搜索二叉树和左树上的最大值或有树上的最小值，但是递归每次返回信息应该是相同的，所以我们每次返回左树和右树是否为搜索二叉树，左树和右树各自的最大最小值

 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  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：

 // 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)
 }