leetcode - insert into a binary search tree(java)

level - medium

[문제 내용]
주어진 bst에 입력값 val을 삽입한 bst를 반환

[example 1]

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

[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]

[해결 방법]
먼저 해당 bst를 위한 TreeNode 구조는 아래와 같다.

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;
        }
    }

작으면 왼쪽 크면 오른쪽에 삽입하도록 하면 되고,
해당 treenode의 왼쪽이나 오른쪽이 비어있을 경우
그 비어 있는 곳에 값을 삽입하고 해당 root를 반환했다.

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        TreeNode parent = root;
        if(root == null) {
            // TreeNode 가 비어있을 경우, root에 값을 삽입
            parent = new TreeNode(val);
            return parent;
        }
        
        while(true) {
            if(root.val < val) {
                if(root.right == null) {
                    // root가 비어있을 경우 삽입
                    root.right = new TreeNode(val);
                    break;
                }
                // 값이 root보다 크면 root를 오른쪽으로 이동
                root = root.right;
            } else if(root.val > val) {
                if(root.left == null) {
                    // root가 비어있을 경우 삽입
                    root.left = new TreeNode(val);
                    break;
                }
                // 값이 root보다 작으면 root를 왼쪽으로 이동
                root = root.left;
            }
        }

        return parent;
    }
}