701. Insert into a Binary Search Tree | LeetCode 문제 풀이

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

Insert into a Binary Search Tree - LeetCode

 

 

문제

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.

 

 

-> 입력할 값이 주어지면 그 값이 들어갈 자리를 찾아 insert한 후 insert한 노드를 반환하면 된다.

 

예제

 

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]

 

 

---

 

풀이

 

• root 노드가 NULL일 경우) 트리의 root 자체가 val값을 가지는 노드가 되는 것이므로  new TreeNode(v)를 해준 후 이를 return 해준다.

 

• v 값이 root->val보다 작을 경우)
  • root->left가 NULL이면) 그 곳에 insert해주고
  • root->left가 NULL이 아니면) insertIntoBST(root->left, v)를 호출해준다.
• v 값이 root->val보다 클 경우)
  • root->right가 NULL이면) 그 곳에 insert해주고
  • root->right가 NULL이 아니면) insertIntoBST(root->right, v)를 호출해준다.

 

 

 

/**
 * 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 v) {
        if (root == NULL) { return new TreeNode(v); } // root 노드가 NULL일 경우, 트리의 root 자체가 val값을 가지는 노드가 되는 것이므로  new TreeNode(v)를 해준 후 이를 return 해준다
        if (v < root->val) {
            if (root->left == NULL) {
                root->left = new TreeNode(v);
            }
            else insertIntoBST(root->left, v);
        }
        else {
            if (root->right == NULL) {
                root->right = new TreeNode(v);
            }
            else insertIntoBST(root->right, v);
        }
        return root;
    }
};