LeetCode 二叉树和递归专题 6：二分搜索树中的问题

回顾二分搜索树的定义

二分搜索树的重要性质

二分搜索树的重要性质如下，初学的时候经常会被忽略或者错误地理解：

• 左子树中所有的结点都小于当前结点；
• 右子树中所有的结点都大于当前结点。
• 以左右孩子为根的子树仍为二分搜索树。

回顾二分搜索树中的基本操作

既然学习到这个专题，我们就有必要来复习巩固之前在学习《二分搜索树》的时候所进行的一些基本操作，这些操作都是十分重要而且基础的。由于二分搜索树的性质，我们总能以 时间复杂度来完成上面的操作。

1、插入 insert

2、查找 find

3、删除 delete

4、最大值，最小值 minimum, maximum

5、前驱，后继 successor, predecessor

6、上界，下界 floor, ceil

7、某个元素的排名 rank

8、寻找第 k大（小）元素 select

9、如何将二分搜索树改造成平衡搜索树，平衡搜索树的一个重要应用就是红黑树。

例题

例1：LeetCode 第 235 题（寻找二分搜索树中指定两个结点的最近公共祖先）

传送门：英文网址：235. Lowest Common Ancestor of a Binary Search Tree ，中文网址：235. 二叉搜索树的最近公共祖先 。

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

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

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

LeetCode 第 235 题（寻找二分搜索树中指定两个结点的最近公共祖先）

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

• 所有节点的值都是唯一的。
• p、q 为不同节点且均存在于给定的二叉搜索树中。

分析：这道题只要我们分析清楚递归关系，其实是非常简单的。就是利用了我们在本文开头部分所叙述的“二分搜索树的重要性质”来进行分类讨论。

1、如果 p、q 结点位于 root 结点的同一侧，如果位于左侧，则递归地调用左孩子，如果位于右侧，则递归地调用右孩子；
2、如果 p、q 结点位于 root 结点的两侧，则所求的最近的公共祖先就是 root 自己；
3、如果 p、q 其中之一位于 root 结点，则 root 结点即为所求的结点。

解答

Java 代码：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null){
            return null;
        }
        if(p.val < root.val && q.val < root.val){
            return lowestCommonAncestor(root.left,p,q);
        }
        if(p.val > root.val && q.val > root.val){
            return lowestCommonAncestor(root.right,p,q);
        }
        return root;
    }
}

总结

这道问题的实现有赖于我们对二分搜索树的深刻的理解以及我们对整个问题的逻辑分析。

相关练习

练习1：LeetCode 第 98 题：验证 BST

传送门：英文网址：98. Validate Binary Search Tree ，中文网址：98. 验证二叉搜索树 。

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

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

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

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

分析：二分搜索树定义 3 条，根据定义判断其实是最简单的，在技巧上就是要分一下，是左子树还是右子树；

练习2：LeetCode 第 450 题：删除二叉搜索树中的节点

传送门：英文网址：450. Delete Node in a BST ，中文网址：450. 删除二叉搜索树中的节点 。

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

1. 首先找到需要删除的节点；
2. 如果找到了，删除它。

说明： 要求算法时间复杂度为 O(h)，h 为树的高度。

示例:

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

    5
   / \
  4   6
 /     \
2       7

另一个正确答案是 [5,2,6,null,4,null,7]。

    5
   / \
  2   6
   \   \
    4   7

分析：删除结点是一个比较复杂的操作，一定要会。给定一棵二分搜索树，删除其中的一个结点。若删除的结点不存在？是否可能有多个需要删除的结点，删除的结点是否需要返回？

这个问题我以前专门写了题解，请点击这里。

练习3： LeetCode 第 108 题： 将有序数组转换为二叉搜索树

传送门：108. 将有序数组转换为二叉搜索树。

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

Python 代码：

# 108. 将有序数组转换为二叉搜索树
# Definition for a binary tree node.
# 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
# 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:

    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """

        if len(nums) == 0:
            return None
        return self.__helper(nums, 0, len(nums) - 1)

    def __helper(self, nums, left, right):
        # 写递归问题是有套路的，先写递归终止条件，然后再写递归流程
        if left > right:
            return None
        if left == right:
            return TreeNode(nums[left])
        mid = left + (right - left) // 2
        root = TreeNode(nums[mid])
        root.left = self.__helper(nums, left, mid - 1)
        root.right = self.__helper(nums, mid + 1, right)
        return root

练习4： LeetCode 第 230 题：二叉搜索树中第K小的元素

传送门：英文网址：230. Kth Smallest Element in a BST ，中文网址：230. 二叉搜索树中第K小的元素 。

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 1

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 3

进阶：
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？

分析：因为二分搜索树具有顺序性，所以我们可以用类似快速排序的 partition 操作来完成

1、二分搜索树的有序性；2、二叉树中序遍历，特别地，二分搜索树的中序遍历得到的是一个有序数组。

简而言之就是在中序遍历的时候数个数，第 1 个遍历到的是第 1 个最小的元素，第 2 个遍历到的是第 2 个最小的元素，数到第 k 个够数了，就不用再遍历了。

Python 代码：

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


# 230. 二叉搜索树中第K小的元素
# 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

class Solution:

    # 使用中序遍历得到 BST 第 k 小的那个元素

    def __init__(self):
        self.k = None
        self.res = None

    def __dfs(self, node):
        if node is None:
            return
        self.__dfs(node.left)
        self.k -= 1
        if self.k == 0:
            self.res = node.val
            return

        self.__dfs(node.right)

    def kthSmallest(self, root, k):
        self.k = k
        self.__dfs(root)
        return self.res

等价写法：

Python 代码：

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def __init__(self):
        self.counter = 0
        self.res = 0

    def kthSmallest(self, root, k):
        # 使用递归的方法，中序遍历
        if root.left:
            # 不是空，才继续遍历
            self.kthSmallest(root.left, k)
        self.counter += 1
        # print(root.val)
        if self.counter == k:
            # 注意：千万不能在这里返回，后序遍历还要继续进行下去
            self.res = root.val
            return
        if root.right:
            self.kthSmallest(root.right, k)
        return self.res

Python 代码：推荐写法

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# 这种写法比 3 更好一些，在入栈的时候，就判断结点是不是空，非空才入栈


class Solution:
    def kthSmallest(self, root, k):
        stack = [(1, root)]
        while stack:
            command, node = stack.pop()
            if command == 0:
                k -= 1
                if k == 0:
                    return node.val
            else:
                # 模拟系统栈实现中序遍历(先左边、再自己、再右边)
                if node.right:
                    stack.append((1, node.right))
                stack.append((0, node))
                if node.left:
                    stack.append((1, node.left))

练习5：LeetCode 第 236 题：二叉树的最近公共祖先

传送门：英文网址：236. Lowest Common Ancestor of a Binary Tree ，中文网址：236. 二叉树的最近公共祖先 。

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

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

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

LeetCode 第 236 题：二叉树的最近公共祖先

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:

• 所有节点的值都是唯一的。
• p、q 为不同节点且均存在于给定的二叉树中。

分析：给定一棵二叉树和两个结点，寻找这两个结点的最近公共祖先。该问题是经典的 LCA 问题。在这里我写了比较完整的分析过程。

（本节完）