二叉搜索树第二期

对于 BST 的大小特性，可以在二叉树中做类似二分搜索的操作，搜索一个元素的效率很高。

代码逻辑如下：

  1. void BST(TreeNode* root, int target) {
  2.     if (root->val == target) {
  3.         // 找到目标，逻辑
  4.     } else if (root->val < target) {
  5.         BST(root->right, target);
  6.     } else {
  7.         BST(root->left, target);
  8.     }
  9. }

01 判断 BST 的合法性

注意，BST 的每个节点应该小于右子树的所有节点。按照下面代码逻辑是不正确的。

  1. bool isValidBST(TreeNode* root) {
  2.     if (root == nullptr)
  3.         return true;
  4.     if (root->left != nullptr && root->val <= root->left->val)
  5.         return false;
  6.     if (root->right != nullptr && root->val >= root->right->val)
  7.         return false;
  8.     return isValid(root->left) && isValid(root->right);
  9. }

出现的问题在于，对于每一个节点 root，代码只检查了它的左右孩子节点是否符合左小右大的原则；但是根据 BST 的定义，root 的整个左子树都要小于 root->val，整个右子树都要大于 root->val。

关键在于，对于某一个节点 root，它只能管得了自己的左右节点，怎么把 root 的约束传递给左右子树？

使用辅助函数，增加函数参数列表，在参数中携带额外信息，将这种约束传递给子树的所有节点。

  1. // 限定以 root 为根的子树节点必须满足 max->val > root->val > min->val
  2. bool isValidBST(TreeNode* root, TreeNode* min, TreeNode* max) {
  3.     // base case
  4.     if (root == nullptr)
  5.         return true;
  6.     // 若 root->val 不符合 max 和 min 的限制，说明不是合法的 BST
  7.     if (min != nullptr && min->val >= root->val)
  8.         return false;
  9.     if (max != nullptr && man->val <= root->val)
  10.         reutrn false;
  11.     // 限定左子树的最大值是 root->val，右子树的最小值为 root->val
  12.     bool left = isValidBST(root->left, min, root);
  13.     bool right = isValidBST(root->right, root, max);
  14.     return left && right;
  15. }

02 二叉搜索树中的搜索

让你在 BST 中搜索值为 target 的节点。函数签名如下：

  1. TreeNode* searchBST(TreeNode* root, int target);

如果是在一棵普通的二叉树中寻找，可以这样写代码：

  1. TreeNode* searchBST(TreeNode* root, int target) {
  2.     if (root == nullptr)
  3.         return nullptr;
  4.     if (root->val == target)
  5.         return root;
  6.     // 当前节点没找到就递归去找左右子树
  7.     TreeNode* left = searchBST(root->left, target);
  8.     TreeNode* right = searchBST(root->right, target);
  9.     return left != nullptr ? left : right;
  10. }

这样写是正确的，但是这段代码穷举了所有节点，适用于所有普通二叉树。

其实不需要递归地搜索两边，类似二分查找思想，根据 target 和 root->val 大小比较，就能排除一边：

  1. TreeNode* searchBST(TreeNode* root, int target) {
  2.     if (root == nullptr)
  3.         return nullptr;
  4.     if (root->val > target) {
  5.         return searchBST(root->left, target);
  6.     } 
  7.     if (root->val < target) {
  8.         return searchBST(root->right, target);
  9.     }
  10.     return root;
  11. }

03 在 BST 中插入一个数

对数据结构的操作无非遍历+访问，遍历就是「找」，访问就是「改」。具体到这个问题，插入一个数，就是先找到插入的位置，然后进行插入操作。一旦涉及「改」，函数就要返回 TreeNode* 类型，并且对递归调用的返回值进行接收

  1. TreeNode* insertIntoBST(TreeNode* root, int val) {
  2.     // 找到空位置插入新节点
  3.     if (root == nullptr) {
  4.         TreeNode* node = new TreeNode(val);
  5.         return node;
  6.     }
  7.     if (root->val < val) {
  8.         root->right = insertIntoBST(root->right, val);
  9.     }
  10.     if (root->val > val) {
  11.         root->left = insertIntoBST(root->left, val);
  12.     }
  13.     return root;
  14. }

04 在 BST 中删除一个数

这个问题较为复杂，跟插入一样，先找再改，框架如下：

  1. TreeNode* deleteNode(TreeNode* root, int key) {
  2.     if (root->val == key) {
  3.         // 进行删除
  4.     } else if (root->val > key) {
  5.         // 去左子树找
  6.         root->left = deleteNode(root->left, key);
  7.     } else if (root->val < key) {
  8.         // 去右子树找
  9.         root->right = deleteNode(root->right, key);
  10.     }
  11.     return root;
  12. }

找到目标节点，比如说是 A，如何删除这个节点，这是个难点。因为删除节点的同时不能破坏 BST 的性质

情况 1：A 恰好是末端节点，两个子节点都为空，那么可以直接删除

2.2.2 二叉搜索树第二期 - 图1

  1. if (root->left == nullptr && root->right == nullptr)
  2.     return nullptr

情况 2：A 只有一个非空子节点，那么让这个孩子接替自己的位置

2.2.2 二叉搜索树第二期 - 图2

  1. // 排除情况 1 之后
  2. if (root->left == nullptr) {
  3.     return root->right;
  4. }
  5. if (root->right == nullptr)
  6.     reutrn root->left;

情况 3：A 有两个子节点。为了不破坏 BST 性质，A 必须找到左子树中最大的那个节点，或者右子树最小的节点来接替字节。以第二种为例：

2.2.2 二叉搜索树第二期 - 图3

  1. if (root->left != nullptr && root->right != nullptr) {
  2.     // 找到右子树中最小节点
  3.     TreeNode* minNode = getMin(root->right);
  4.     minNode->left = root->left;
  5.     TreeNode* tmp = root;
  6.     root = root->right;
  7.     delete tmp;
  8.     return root;
  9. }

三种情况分析完毕，填入框架：

  1. TreeNode* getMin(TreeNode* root) {
  2.     while (root->left != nullptr)
  3.         root = root->left;
  4.     return root;
  5. }
  7. TreeNode* deleteNode(TreeNode* root, int key) {
  8.     if (root == nullptr) {
  9.         return nullptr;
  10.     }
  11.     if (root->val == key) {
  12.         // 两种 if 将情况 1 和情况 2 都处理了
  13.         if (root->left == nullptr)
  14.             return root->right;
  15.         if (root->right == nullptr)
  16.             return root->left;
  17.         // 处理情况 3
  18.         TreeNode* minNode = getMin(root->right);
  19.         minNode->left = root->left;
  20.         TreeNode* tmp = root;
  21.         root = root->right;
  22.         delete tmp;
  23.         return root;
  24.     } else if (root->val > key) {
  25.         root->left = deleteNode(root->left, key);
  26.     } else if (root->val < key) {
  27.         root->right = deleteNode(root->right, key);
  28.     }
  29.     return root;
  30. }