力扣 701. 二叉搜索树中的插入操作-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣 701. 二叉搜索树中的插入操作。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目来源：https://leetcode.cn/problems/insert-into-a-binary-search-tree/description/

力扣 701. 二叉搜索树中的插入操作,开始C++吧,leetcode,算法,c++,数据结构,二叉树

思路：只要根据二叉搜索树的特性，将新插入节点的值不断地与树节点值进行比较，然后找到新节点所属的叶子节点位置，插入即好，返回根节点。

C++题解1：迭代法。需要用一个指针保存父节点。

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

C++题解2：递归法，递归函数有返回值。来源代码随想录

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

C++题解3：递归法，递归函数没有返回值，需要记录上一个节点（父节点）。来源代码随想录文章来源地址https://www.toymoban.com/news/detail-516665.html

class Solution {
private:
    TreeNode* parent;
    void traversal(TreeNode* cur, int val) {
        if (cur == NULL) {
            TreeNode* node = new TreeNode(val);
            if (val > parent->val) parent->right = node;
            else parent->left = node;
            return;
        }
        parent = cur;
        if (cur->val > val) traversal(cur->left, val);
        if (cur->val < val) traversal(cur->right, val);
        return;
    }

public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        parent = new TreeNode(0);
        if (root == NULL) {
            root = new TreeNode(val);
        }
        traversal(root, val);
        return root;
    }
};

到了这里，关于力扣 701. 二叉搜索树中的插入操作的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！