[LeetCode] 701. Insert into a Binary Search Tree - 문제풀이

Description

주어진 이진 검색 트리에서 특정 값을 올바른 노드에 삽입 후 root를 반환하는 문제입니다.

You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

Example 1:

Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Explanation: Another accepted tree is:

Example 2:

Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]

Example 3:

Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
Output: [4,2,7,1,3,5]

Constraints:

• The number of nodes in the tree will be in the range [0, 104].
• -10^8 <= Node.val <= 10^8
• All the values Node.val are unique.
• -10^8 <= val <= 10^8
• It's guaranteed that val does not exist in the original BST.

Solution 1. Recursion (재귀)

public TreeNode insertIntoBST(TreeNode root, int val) {

    //1. Recursion
    if(root==null) return new TreeNode(val);
    if(root.val > val){
        root.left = insertIntoBST(root.left,val);
    }else{
        root.right = insertIntoBST(root.right,val);
    }
    return root;
}

재귀호출을 통해 이진검색트리의 값을 비교해본뒤 타겟보다 크면 오른쪽노드에 붙여야 하므로 오른쪽으로 재귀호출, 반대는 왼쪽으로 재귀호출하여 마지막 노드에 다다를 경우 새로운 노드를 추가하여 반환합니다.

Solution 2. Iteration (반복)

public TreeNode insertIntoBST(TreeNode root, int val) {

    //2. Iteration
    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;
}

root의 값을 체크하여 타겟보다 root가 크면 왼쪽, 아니면 오른쪽으로 이동해가며 마지막에 도달했을떄(null) 새로운 노드를 반환하여 root를 리턴해줍니다.

Reference

Insert into a Binary Search Tree - LeetCode