LeetCode 701(Insert into a Binary Search Tree, java)

0. 문제

https://leetcode.com/problems/insert-into-a-binary-search-tree/

Insert into a Binary Search Tree - LeetCode

 

1. 문제 설명

- 문제에서 이진탐색트리(= root)와 정수(= val)가 주어진다.

- 이 문제는 문제에서 주어진 정수(= val)를 이진탐색트리에 삽입하는 것이 핵심이다. 

 

2. 문제 해설

a) 첫 번째 접근

- 이진 탐색 트리의 특징을 이용하여 트리를 탐색한다.

- 탐색 과정에서 노드의 value와 정수(= val)를 비교하여, 좌측 또는 우측을 탐색한다.

- 자식 노드를 탐색하는 과정에서 해당 노드가 null인 경우, 새로운 노드를 삽입한다.

 

- 이 과정을 재귀 함수로 구현하면 끝이다.

- 다음 코드를 보면서 이해해보자. 

 

3. 정답 코드

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