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

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

难度：$middle$

题目描述

给定二叉搜索树（BST）的根节点 $root$ 和要插入树中的值 $value$ ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 树中的节点数将在 $[0,10^4]$的范围内。
• $-10^8<=Node.val<=10^8$
• 所有值 $Node.val$ 是 独一无二 的。
• $-10^8<=val<=10^8$
• 保证 $val$ 在原始BST中不存在。

算法1

(递归)

• 若 root 为空则返回当前 val 值的新节点；
• 若 root.val > val，说明需要在左边插入一个新的节点，递归左子树；
• 若 root.val < val，说明需要在右边插入一个新的节点，递归右子树。

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是二叉搜索树的节点数。

• 空间复杂度 : $O(n)$

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (!root) return new TreeNode(val);
        if (root->val > val) root->left = insertIntoBST(root->left, val);
        else root->right = insertIntoBST(root->right, val);
        return root;
    }
};

算法2

(数据结构基础、模拟)

1. 按照二叉搜索树的性质，自顶向下查找插入的位置。
2. 如果查找过程中发现相同的值，则直接返回。
3. 如果 val 小于当前结点的值，则向左儿子查找；否则向右儿子查找，最后插入到叶结点上。
4. 注意树为空的情况。

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是二叉搜索树的节点数。

• 空间复杂度 : $O(n)$，只需要新创建一个待插入的结点。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (!root)
            return new TreeNode(val);

        TreeNode *cur = root, *fa = NULL;
        while (cur) {
            if (val == cur -> val)
                return root;
            else if (val < cur -> val) {
                fa = cur;
                cur = cur -> left;
            } else {
                fa = cur;
                cur = cur -> right;
            }
        }
        if (val < fa -> val)
            fa -> left = new TreeNode(val);
        else
            fa -> right = new TreeNode(val);

        return root;
    }
};