二叉树

树是一种非线性表结构比线性表的数据结构要复杂得多。

树的定义

树的定义

“树”中每个元素叫作“节点”；用来连线相邻节点之间的关系，叫作“父子关系”。

如下图所示：

1. A 节点就是 B 节点的父节点，B 节点是 A 节点的子节点。

2. B、C、D 这三个节点的父节点是同一个节点，所以它们之间互称为兄弟节点。

3. 没有父节点的节点叫作根节点，如图中的节点 E。

4. 没有子节点的节点叫作叶节点，如图中的 G、H、I、J、K、L 都是叶子节点。

树

树还有三个比较相似的概念：

• 高度（Height）：节点到叶子节点的最长路径（边数），从下往上看，起点为0

• 深度（Depth）：根节点到这个节点所经历的边的个数，从上往下看，起点为0

• 层（Level）：节点深度+1，从上往下看，起点为1

树的高度：根节点的高度+1

高度、深度、层

二叉树的定义

二叉树，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。

二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。

二叉树

如上图所示：

• 编号 2 的二叉树中，叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫作满二叉树。

• 编号 3 的二叉树中，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作完全二叉树。

存储二叉树

要理解完全二叉树定义的由来，需要先了解，如何表示（或者存储）一棵二叉树。想要存储一棵二叉树，有两种方法：

• 一种是基于指针的二叉链式存储法

• 一种是基于数组的顺序存储法

链式存储

链式存储

从图可以看到，每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。

只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。这种存储方式比较常用，大部分二叉树代码都是通过这种结构来实现的。

顺序存储

顺序存储

基于数组的顺序存储法。

1. 把根节点存储在下标 i=1 的位置

2. 左子节点存储在下标 2*i=2 的位置

3. 右子节点存储在下标 2*i+1=3 的位置

4. 以此类推

所以，图中 D 节点的左子节点存储在 2*i=2*2=4 的位置，右子节点存储在 2*i+1=2*2+1=5 的位置。

如果节点 X 存储在数组中下标为 i 的位置：

• 下标为 2*i 的位置存储的就是左子节点

• 下标为 2*i+1 的位置存储的就是右子节点

• 下标为 i/2 的位置存储就是它的父节点

通过这种方式，我们只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置），这样就可以通过下标计算，把整棵树都串起来。

如果是一棵完全二叉树只会浪费下标为0的存储位置，如果是一棵非完全二叉树会浪费较多存储空间。

顺序存储浪费的存储空间

所以，如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。

这也是为什么完全二叉树要求最后一层的子节点都靠左的原因。堆其实就是一种完全二叉树，最常用的存储方式就是数组。

遍历二叉树

如何将所有节点都遍历打印出来，经典的方法有三种，前序遍历、中序遍历和后序遍历。其中，前、中、后序，表示的是节点与它的左右子树节点遍历打印的先后顺序。

• 前序遍历：对于树中的任意节点，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。

• 中序遍历：对于树中的任意节点，先打印它的左子树，然后再打印它本身，最后打印它的右子树。

• 后序遍历：对于树中的任意节点，先打印它的左子树，然后再打印它的右子树，最后打印它本身。

遍历二叉树

实际上，二叉树的前、中、后序遍历就是一个递归的过程。

递归的关键是递推公式和终止条件，递推公式的关键是问题拆分，如果要解决问题 A，就假设子问题 B、C 已经解决，然后再来看如何利用 B、C 来解决 A。

# 前序遍历的递推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)

# 中序遍历的递推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)

# 后序遍历的递推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r

# 伪代码
void preOrder(Node* root) {
  if (root == null) return;
  print root // 此处为伪代码，表示打印root节点
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(Node* root) {
  if (root == null) return;
  inOrder(root->left);
  print root // 此处为伪代码，表示打印root节点
  inOrder(root->right);
}

void postOrder(Node* root) {
  if (root == null) return;
  postOrder(root->left);
  postOrder(root->right);
  print root // 此处为伪代码，表示打印root节点
}

二叉树遍历的时间复杂度是O(n)。

二叉查找树

二叉查找树最大的特点就是，支持动态数据集合的快速插入、删除、查找操作。

散列表也是支持这些操作的，并且散列表的这些操作比二叉查找树更高效，时间复杂度是 O(1)。

二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树，是为了实现快速查找而生的。它还支持快速插入、删除一个数据。这些都依赖于二叉查找树的特殊结构。二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

二叉查找树

查找操作

1. 先取根节点，如果它等于我们要查找的数据，那就返回

2. 如果要查找的数据比根节点的值小，那就在左子树中递归查找

3. 如果要查找的数据比根节点的值大，那就在右子树中递归查找

插入操作

插入过程有点类似查找操作。

1. 新插入的数据一般都是在叶子节点上，所以只需要从根节点开始，依次比较要插入的数据和节点的大小关系

2. 如果要插入的数据比节点的数据大

   1. 如果节点的右子树为空，就将新数据直接插到右子节点的位置

   2. 如果节点的右子树不为空，就再递归遍历右子树，查找插入位置

3. 如果要插入的数据比节点数值小

   1. 如果节点的左子树为空，就将新数据插入到左子节点的位置

   2. 如果不为空，就再递归遍历左子树，查找插入位置

删除操作

删除操作就比较复杂。针对要删除节点的子节点个数的不同，分三种情况来处理：

1. 第一种情况是，如果要删除的节点没有子节点，只需要直接将父节点中，指向要删除节点的指针置为 null。比如图中的删除节点 55。

2. 第二种情况是，如果要删除的节点只有一个子节点（只有左子节点或者右子节点），只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。比如图中的删除节点 13。

3. 第三种情况是，如果要删除的节点有两个子节点，这就比较复杂了。需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，可以应用上面两条规则来删除这个最小节点。比如图中的删除节点 18。

二叉查找树的删除操作

实际上，关于二叉查找树的删除操作，还有个非常简单、取巧的方法，就是单纯将要删除的节点标记为“已删除”，但是并不真正从树中将这个节点去掉。这样原本删除的节点还需要存储在内存中，比较浪费内存空间，但是删除操作就变得简单了很多。而且，这种处理方法也并没有增加插入、查找操作代码实现的难度。

其他操作

二叉查找树中快速地查找最大节点和最小节点、前驱节点和后继节点。

中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 O(n)，非常高效。因此，二叉查找树也叫作二叉排序树。

时间复杂度分析

二叉查找树的时间复杂度分析

图中第一种二叉查找树，根节点的左右子树极度不平衡，已经退化成了链表，所以查找的时间复杂度就变成了 O(n)。

大部分情况下，不管操作是插入、删除还是查找，时间复杂度其实都跟树的高度成正比，也就是 O(height)。将高度转为层数，第 K 层包含的节点个数就是 2^(K-1)。最后一层的节点个数在 1 个到 2^(L-1) 个之间（假设最大层数是 L）。

所以得到如下公式：

n >= 1+2+4+8+...+2^(L-2)+1
n <= 1+2+4+8+...+2^(L-2)+2^(L-1)

借助等比数列的求和公式，可以计算出，L 的范围是[$log_2{(n+1)}$, $log_2{n}$+1]`。

需要构建一种不管怎么删除、插入数据，在任何时候，都能保持任意节点左右子树都比较平衡的二叉查找树，这就是平衡二叉查找树。平衡二叉查找树的高度接近 logn，所以插入、删除、查找操作的时间复杂度也比较稳定，是 O(logn)。

支持重复数据的二叉查找树

在实际的软件开发中，二叉查找树中存储的，是一个包含很多字段的对象。利用对象的某个字段作为键值（key）来构建二叉查找树，把对象中的其他字段叫作卫星数据。

插入操作

如果存储的两个对象键值相同，有两种解决方法：

1. 第一种方法比较容易。二叉查找树中每一个节点不仅会存储一个数据，因此通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。

2. 第二种方法比较不好理解，不过更加优雅。每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，就将这个要插入的数据放到这个节点的右子树，即把这个新插入的数据当作大于这个节点的值来处理。

查找操作

当要查找数据的时候，遇到值相同的节点，并不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点，才停止。这样就可以把键值等于要查找值的所有节点都找出来。

删除操作

对于删除操作，需要先查找到每个要删除的节点，然后再按前面讲的删除操作的方法，依次删除。

二叉查找树与散列表的对比

• 散列表的插入、删除、查找操作的时间复杂度可以做到常量级的 O(1)，非常高效

• 二叉查找树在比较平衡的情况下，插入、删除、查找操作时间复杂度才是 O(logn)

数据有序性

• 散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序

• 二叉查找树只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列

稳定性

• 散列表扩容耗时很多，当遇到散列冲突时，性能不稳定

• 二叉查找树的性能不稳定，但在工程中最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)

执行效率

• 散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快

• 加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高

复杂度

散列表的构造比二叉查找树要复杂，需要考虑的东西很多，比如：

• 散列函数的设计

• 冲突解决办法

• 扩容

• 缩容

平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。

存储空间利用率

为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。

平衡二叉查找树在某些方面还是优于散列表的，所以，这两者的存在并不冲突。在实际的开发过程中，需要结合具体的需求来选择使用哪一个。

常考考点

二叉树的最大深度

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

思路

利用递归的思路，二叉树的最大深度就是左右子树最大深度+1。

示例代码

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }

    return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

func max(i, j int) int {
    if i > j {
        return i
    }
    return j
}

平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

思路

使用分治法。

1. 左子树平衡，右子树平衡，并且左右两边高度差小于或等于1，那么就是平衡二叉树

因为需要返回是否平衡及高度，要么返回两个数据，要么合并两个数据， 所以用-1 表示不平衡，>0 表示树高度（二义性：一个变量有两种含义）。

示例代码

func isBalanced(root *TreeNode) bool {
    if maxDepth(root) == -1 {
        return false
    }
    return true
}

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left := maxDepth(root.Left)
    right := maxDepth(root.Right)

    if left == -1 || right == -1 || left-right > 1 || right-left > 1 {
        return -1
      }

    if left > right {
        return left + 1
    }
    return right + 1
}

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

思路

使用分治法，存在左子树的公共祖先或者存在右子树的公共祖先，就返回子树的祖先，否则返回根节点

示例代码

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil {
        return root
    }

    if p == root || q == root {
        return root
    }

    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)

  // 说明两个节点分别在两棵子树上
    if left != nil && right != nil {
        return root
    }

  // 说明这里两个节点在右子树上
    if left == nil {
        return right
    }

  // 说明这两个节点在左子树上
    if right == nil {
        return left
  }

    return nil
}

二叉树的层序遍历

给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。

思路

使用一个队列来保存当前节点的子节点，也就是下一层的节点。时间复杂度是O(logn)。

示例代码

func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }

    queue := make([]*TreeNode, 0)
    queue = append(queue, root)

    res := make([][]int, 0)
    for len(queue) != 0 {
        size := len(queue) // 获取当前层中节点数
        tmp := make([]int, 0) // 保存当前层中的结果
        for i := 0; i < size; i++ {
            cur := queue[0]
            queue = queue[1:]
            tmp = append(tmp, cur.Val)
            if cur.Left != nil {
                queue = append(queue, cur.Left)
            }
            if cur.Right != nil {
                queue = append(queue, cur.Right)
            }
        }
        res = append(res, tmp)
    }
    return res
}

二叉树的层序遍历【变体1】

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）。

思路

与上面层序遍历的操作一样，唯一的区别是输出结果的时候需要反向输出，因此可以定义一个reserve函数。

注意：结果直接保存在切片中，reserve函数直接通过切片的索引进行修改是可以直接对底层数组生效的。

示例代码

func levelOrderBottom(root *TreeNode) [][]int {
    res := make([][]int, 0)
    if root == nil {
        return res
    }

    queue := make([]*TreeNode, 0)
    queue = append(queue, root)

    for len(queue) > 0 {
        size := len(queue)
        tmp := make([]int, 0)
        for i := 0; i < size; i++ {
            cur := queue[0]
            queue = queue[1:]
            tmp = append(tmp, cur.Val)
            if cur.Left != nil {
                queue = append(queue, cur.Left)
            }
            if cur.Right != nil {
                queue = append(queue, cur.Right)
            }
        }
        res = append(res, tmp)
    }
    reserve(res)
    return res
}

func reserve(res [][]int) {
    n := len(res)
    for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
        res[i], res[j] = res[j], res[i]
    }
}

二叉树的锯齿形层次遍历

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

思路

层序遍历的基础还是不变，只是在输出结果的时候要进行一些操作，有两种方式可以实现：

1. 在获取每一个的结果之后，直接判断该层是否需要翻转（使用标志位来判断是否翻转，默认为false）

2. 获取全部层序输出结果之后，在对结果中的一部分进行翻转（使用奇偶性来判断是否翻转，奇数翻转）

示例代码

func zigzagLevelOrder(root *TreeNode) [][]int {
    res := make([][]int, 0)
    if root == nil {
        return res
    }

    queue := make([]*TreeNode, 0)
    queue = append(queue, root)
    flag := false
    for len(queue) > 0 {
        size := len(queue)
        level := make([]int, 0)
        for i := 0; i < size; i++ {
            cur := queue[0]
            queue = queue[1:]
            level = append(level, cur.Val)
            if cur.Left != nil {
                queue = append(queue, cur.Left)
            }
            if cur.Right != nil {
                queue = append(queue, cur.Right)
            }
        }
        if flag {
            reverseLevel(level)
        }
        res = append(res, level)
        flag = !flag
    }
    // reverseRes(res)
    return res
}

func reverseLevel(level []int) {
    n := len(level)
    for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
        level[i], level[j] = level[j], level[i]
    }
}

func reverseRes(res [][]int) {
    n := len(res)
    for i := 0; i < n; i++ {
        if i%2 != 0 {
            n := len(res[i])
            for k, j := 0, n-1; k < j; k, j = k+1, j-1 {
                res[i][k], res[i][j] = res[i][j], res[i][k]
            }
        }
    }
}

验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

1. 节点的左子树只包含小于当前节点的数。

2. 节点的右子树只包含大于当前节点的数。

3. 所有左子树和右子树自身必须也是二叉搜索树。

思路

二叉搜索树的定义：左边节点都小于根节点，右边节点都大于根节点。

有两种方式可以验证：

1. 根据定义可知，二叉搜索树的中序遍历是一个升序结果，判断结果来验证是否而二叉搜索树

2. 根据定义，递归判断每一棵子树是否满足定义，都满足则成立，不满足则不成立（判断是的时候需要左子树的最大节点小于root，有子树的最小节点大于root，因此创建一个结构体来存储子树判断结果）

示例代码

// 思路1
func isValidBST(root *TreeNode) bool {
    res := make([]int, 0)
    inOrder(root, &res)
    for i := 0; i < len(res)-1; i++ {
        if res[i] >= res[i+1] {
            return false
        }
    }
    return true
}

func inOrder(root *TreeNode, res *[]int) {
    if root == nil {
        return
    }
    inOrder(root.Left, res)
    *res = append(*res, root.Val)
    inOrder(root.Right, res)
}

// 思路2
type result struct {
    isValid bool
    Max     *TreeNode
    Min     *TreeNode
}

func isValidBST(root *TreeNode) bool {
    res := isValidSub(root)
    return res.isValid
}

func isValidSub(root *TreeNode) result {
    res := result{}

    if root == nil {
        res.isValid = true
        return res
    }

    left := isValidSub(root.Left)
    right := isValidSub(root.Right)

    if !left.isValid || !right.isValid {
        res.isValid = false
        return res
    }

    if left.Max != nil && left.Max.Val >= root.Val {
        res.isValid = false
        return res
    }

    if right.Min != nil && right.Min.Val <= root.Val {
        res.isValid = false
        return res
    }

    res.isValid = true
    res.Min = root
    if left.Min != nil {
        res.Min = left.Min
    }
    res.Max = root
    if right.Max != nil {
        res.Max = right.Max
    }
    return res
}

二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。

思路

使用深度优先搜索来寻找待插入的位置（当前节点为空时，用待插入值新建节点并接入），根据二叉搜索树中值的性质：

1. 待插入值大于当前节点值，则再右边寻找位置

2. 待插入值小于当前节点值，则再左边寻找位置

示例代码

func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        root = &TreeNode{Val: val}
        return root
    }

    if root.Val > val {
        root.Left = insertIntoBST(root.Left, val)
    } else {
        root.Right = insertIntoBST(root.Right, val)
    }
    return root
}