leetcode：701. 二叉搜索树中的插入操作

题目

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

示例 1：
[中等] 701. 二叉搜索树中的插入操作 - 图1

  1. 输入：root = [4,2,7,1,3], val = 5
  2. 输出：[4,2,7,1,3,5]
  3. 解释：另一个满足题目要求可以通过的树是：

示例 2：

  1. 输入：root = [40,20,60,10,30,50,70], val = 25
  2. 输出：[40,20,60,10,30,50,70,null,null,25]

示例 3：

  1. 输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
  2. 输出：[4,2,7,1,3,5]

解答 & 代码

本题无需考虑插入后二叉搜索树的平衡性，因此总能搜索到一个叶子节点，新建一个 val 值节点插入到该节点之后。
递归搜索二叉搜索树：

  1. 递归结束条件：如果当前根节点为空，则在此处新建一个 val 值节点并直接返回这个新节点，完成插入
  2. 如果当前根节点的值大于 val，则说明 val 应该插入到左子树，因此递归搜索左子树

  3. 否则，如果当前根节点的值小于 val，则说明 val 应该插入到右子树，因此递归搜索右子树

    1. /**
    2. * Definition for a binary tree node.
    3. * struct TreeNode {
    4. *     int val;
    5. *     TreeNode *left;
    6. *     TreeNode *right;
    7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10. * };
    11. */
    12. class Solution {
    13. public:
    14.  TreeNode* insertIntoBST(TreeNode* root, int val) {
    15.      // 递归结束条件：如果当前根节点为空，则在此处新建一个 val 值节点并直接返回这个新节点，完成插入
    16.      if(root == nullptr)
    17.          return new TreeNode(val);
    19.      // 如果当前根节点的值大于 val，则说明 val 应该插入到左子树，因此递归搜索左子树
    20.      if(root->val > val)
    21.          root->left = insertIntoBST(root->left, val);
    22.      // 如果当前根节点的值小于 val，则说明 val 应该插入到右子树，因此递归搜索右子树
    23.      else if(root->val < val)
    24.          root->right = insertIntoBST(root->right, val);
    25.      return root;
    26.  }
    27. };

    复杂度分析：设二叉搜索树节点数为 N

  • 时间复杂度 O(log N)：只会遍历一条路径到叶子节点，因此时间复杂度相当于二叉搜索树的深度（或者也可以理解为二分查找）
  • 空间复杂度 O(log N)：递归栈空间复杂度取决于树深度

执行结果：

  1. 执行结果：通过
  3. 执行用时：80 ms, 在所有 C++ 提交中击败了 80.69% 的用户
  4. 内存消耗：55.6 MB, 在所有 C++ 提交中击败了 29.36% 的用户