701-kir3i.md

701. Insert into a Binary Search Tree

Solution

• 시간복잡도: O(N)

• 알고리즘

  자료구조, BST

• 풀이설명

  BST에 새로운 노드를 추가하는 함수를 구현하는 문제입니다. BST의 특성에 따라 구현하면 됩니다.

• 소스코드

  • C++

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

  • Python

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

  • Java

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