二叉搜索树 #

一、基本操作 #

1、合法性 #

98. 验证二叉搜索树

• 当前节点的值必须大于左子树所有的值（即左子树的最大值）
• 借助辅助函数，传递信息/约束

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return isValidBST(root, nullptr, nullptr);
    }

    bool isValidBST(TreeNode* root, TreeNode* leftMax, TreeNode* rightMin) {
        if (root == nullptr) return true;
        // 当前节点的值必须大于左子树所有的值（即左子树的最大值）
        if (leftMax != nullptr && root->val <= leftMax->val) return false;
        // 必须小于右子树所有的值（即右子树的最小值）
        if (rightMin != nullptr && root->val >= rightMin->val) return false; 

        // 对左子树递归时，左子树的左子树沿用，右子树就是当前节点
        return isValidBST(root->left, leftMax, root) && isValidBST(root->right, root, rightMin);
    }
};

2、遍历搜索 #

• 二叉搜索树中的搜索

  • 类似二分搜索
  Expand ↕

  ```C++
  class Solution {
  public:
      TreeNode* searchBST(TreeNode* root, int val) {
          if (root == nullptr) return nullptr;
          if (root->val > val) return searchBST(root->left, val);
          if (root->val < val) return searchBST(root->right, val);
          return root;
      }
  };
  ```
  

• 二叉搜索树中第K小的元素

  直观的：

  1. 中序遍历本身就是升序的；
  2. 所以中序遍历，记录当前遍历到第几个，和 k 比较。
  Expand ↕

  ```C++
  class Solution {
  public:
      int kthSmallest(TreeNode* root, int k) {
          traverse(root, k);
          return res;
      }
  private:
      int res = 0;
      int rank = 0;
      void traverse(TreeNode *root, int k) {
          if (root == nullptr) return;
          traverse(root->left, k);
          rank++;
          if (k == rank) {
              res = root->val;
              return;
          }
          traverse(root->right, k);
      }
  };
  ```
  

  优化：

  1. 这样的话，每调用一次就要遍历一次，复杂度O(N)；
  2. 想办法降到O(logN)，二分的方法：如果当前节点排名 m, 和 k 去比较，不相等的就在左/右子树；
  3. 因此每个节点需要维护额外的信息：以自己为根的树有多少个节点。

• 把二叉搜索树转换为累加树

  1. 倒着累加就行；
  2. 降序遍历时，先右子树，再左子树就可以。
  Expand ↕

  ```C++
  class Solution {
  public:
      TreeNode* convertBST(TreeNode* root) {
          traverse(root);
          return root;
      }
      int sum = 0;
      void traverse(TreeNode root) {
          if (root == null) {
              return;
          }
          traverse(root.right);
          sum += root.val;
          root.val = sum;
          traverse(root.left);
      }
  };
  ```
  

增 #

二叉搜索树中的插入操作

• 细节要注意。

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == nullptr) return new TreeNode(val);
        if (val < root->val) root->left = insertIntoBST(root->left, val);
        if (val > root->val) root->right = insertIntoBST(root->right, val);
        return root;
    }
};