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

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

#树 2024-11-14

class Solution {
public:
    void insert(TreeNode* root, int val) {
        int cur = root->val;
        if (root->left == nullptr && root->right == nullptr) {	// 插入
            TreeNode* node = new TreeNode(val);
            val < cur ? root->left = node : root->right = node;
        } else if (root->left == nullptr && val < cur) {
            TreeNode* node = new TreeNode(val);
            root->left = node;
        } else if (root->right == nullptr && val > cur) {
            TreeNode* node = new TreeNode(val);
            root->right = node;
        } else {
            val < cur ? insert(root->left, val) : insert(root->right, val);	// 递归查询
        }
    }
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == nullptr) {	// 如果为空节点，那就把待插入的 val 加入到空树中作为 root 节点
            root = new TreeNode(val);
        } else {
            insert(root, val);
        }
        return root;
    }
};

我们插入元素，不需要考虑调整，插入的时候就插在最后面就可以，考虑到下面三种可以插入的情况：

• 如果当前节点有左右孩子，那就必然是不能插入，也必然进入递归中，即 else 语句
• 如果当前节点没有左右孩子，那是必然可以插入，只需要把目标值和当前值进行比较之后，选择插入左边还是右边
• 如果当前节点右节点可插入，且目标值大于当前值，则确认可以插入到右边
• 如果当前节点左节点可插入，且目标值小于当前值，则确认可以插入到左边

最后就是一个特殊情况，即 为空树，对于这种就直接把待插入的 val 加入到空树中作为 root 节点。