讨论/《二叉搜索树》 - 二叉搜索树中的插入操作/
《二叉搜索树》 - 二叉搜索树中的插入操作
共 7 个回复

简单题

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
            TreeNode treeNode=root;
            TreeNode treeNode1 = new TreeNode(val);
            while(true){
                if(root==null){
                    treeNode=treeNode1;
                    break;
                }
                if(root.val>val){
                    if(root.left==null){
                        root.left=treeNode1;
                        break;
                    }
                    root=root.left;
                }else if(root.val<val){
                    if(root.right==null){
                        root.right=treeNode1;
                        break;
                    }
                    root=root.right;
                }
            }
            return treeNode;
        }
}

c5170cfbe2a2c9cf684ee1627dd486c.png

2
class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root:
            return TreeNode(val)
        if val < root.val:
            root.left = self.insertIntoBST(root.left, val)
        else:
            root.right = self.insertIntoBST(root.right, val)
        return root
1

简单题, 直接遍历树

/**
 * 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) {
        TreeNode* ret = root;
        while(root != nullptr && root->val != NULL)
        {
            if(root->val < val)
            {
                if(root->right == nullptr)
                {
                    root->right = new TreeNode(NULL);
                }
                root = root->right;
            }
            else
            {
                if(root->left == nullptr)
                {
                   root->left = new TreeNode(NULL); 
                }
                root = root->left;
            }
        }
        if(ret == nullptr)
        {
            ret = new TreeNode(val);
        }
        else{
            root->val = val;
        }
        return ret;
    }
};
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root == NULL) {
            return new TreeNode(val);
        }
        if(val < root->val) {
            root->left = insertIntoBST(root->left, val);
        } else {
            root->right = insertIntoBST(root->right, val);
        }
        return root;
    }
};
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null) return new TreeNode(val);

        TreeNode cur = root;
        while(cur != null){
            if(cur.val > val) {
                if(cur.left == null){
                    cur.left = new TreeNode(val);
                    break;
                } else {
                    cur = cur.left;
                }
            } else {
                if(cur.right == null){
                    cur.right = new TreeNode(val);
                    break;
                } else {
                    cur = cur.right;
                }
            }
        }

        return root;
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        root = insert(root, val);
        return root;
    }

    private TreeNode insert(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        int cmp = val - root.val;
        if (cmp == 0) {

        } else if (cmp < 0) {
            root.left = insert(root.left, val);
        } else {
            root.right = insert(root.right, val);
        }
        return root;
    }

}
1

Java

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        TreeNode newNode = new TreeNode(val);
        TreeNode curr = root;
        if(curr == null)return newNode;
        while(true){
            if(val<curr.val){
                if(curr.left == null){
                    curr.left = newNode;
                    return root;
                }else{
                    curr = curr.left;
                }
            }else{
                if(curr.right == null){
                    curr.right = newNode;
                    return root;
                }else{
                    curr = curr.right;
                }
            }
        }
    }
}