二叉树

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

树的定义

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

如下图所示：

A 节点就是 B 节点的父节点，B 节点是 A 节点的子节点。
B、C、D 这三个节点的父节点是同一个节点，所以它们之间互称为兄弟节点。
没有父节点的节点叫作根节点，如图中的节点 E。
没有子节点的节点叫作叶节点，如图中的 G、H、I、J、K、L 都是叶子节点。

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

高度（Height）：节点到叶子节点的最长路径（边数），从下往上看，起点为0
深度（Depth）：根节点到这个节点所经历的边的个数，从上往下看，起点为0
层（Level）：节点深度+1，从上往下看，起点为1

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

二叉树的定义

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

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

如上图所示：

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

存储二叉树

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

一种是基于指针的二叉链式存储法
一种是基于数组的顺序存储法

链式存储

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

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

顺序存储

基于数组的顺序存储法。

把根节点存储在下标 i=1 的位置
左子节点存储在下标 2*i=2 的位置
右子节点存储在下标 2*i+1=3 的位置
以此类推

所以，图中 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. 如果节点的右子树不为空，就再递归遍历右子树，查找插入位置
如果要插入的数据比节点数值小
1. 如果节点的左子树为空，就将新数据插入到左子节点的位置
2. 如果不为空，就再递归遍历左子树，查找插入位置

删除操作

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

第一种情况是，如果要删除的节点没有子节点，只需要直接将父节点中，指向要删除节点的指针置为 null。比如图中的删除节点 55。
第二种情况是，如果要删除的节点只有一个子节点（只有左子节点或者右子节点），只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。比如图中的删除节点 13。
第三种情况是，如果要删除的节点有两个子节点，这就比较复杂了。需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，可以应用上面两条规则来删除这个最小节点。比如图中的删除节点 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）来构建二叉查找树，把对象中的其他字段叫作卫星数据。

插入操作

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

第一种方法比较容易。二叉查找树中每一个节点不仅会存储一个数据，因此通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。
第二种方法比较不好理解，不过更加优雅。每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，就将这个要插入的数据放到这个节点的右子树，即把这个新插入的数据当作大于这个节点的值来处理。

查找操作

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

删除操作

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

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

散列表的插入、删除、查找操作的时间复杂度可以做到常量级的 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 表示不平衡，>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]
    }
}

二叉树的锯齿形层次遍历

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

思路

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

在获取每一个的结果之后，直接判断该层是否需要翻转（使用标志位来判断是否翻转，默认为false）
获取全部层序输出结果之后，在对结果中的一部分进行翻转（使用奇偶性来判断是否翻转，奇数翻转）

示例代码

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]
            }
        }
    }
}

验证二叉搜索树

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

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

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

思路

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

有两种方式可以验证：

根据定义可知，二叉搜索树的中序遍历是一个升序结果，判断结果来验证是否而二叉搜索树
根据定义，递归判断每一棵子树是否满足定义，都满足则成立，不满足则不成立（判断是的时候需要左子树的最大节点小于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）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。保证原始二叉搜索树中不存在新值。

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

思路

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

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

示例代码

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
}

最后更新于4年前

这有帮助吗？