700. Search in a Binary Search Tree | LeetCode 문제 풀이

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

Search in a Binary Search Tree - LeetCode

 

 

문제

 

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

 

-> val 값을 입력받은 후, 트리에서 해당 val값을 가지고 있는 노드가 있을 경우 그 노드를 return하면 된다.

 

예제

 

Example 1:

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

Example 2:

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

 

 

---

 

 

풀이

 

재귀를 이용하였다!

 

• 끝까지 search 했는데도 찾지 못 했을 경우) NULL을 return
• val값을 가진 노드를 찾을 경우) 해당 노드를 return
• 위의 두 상황에 해당하지 않는 경우) root->val 값과 val의 대소비교를 하여
  • val이 root->val보다 작을 경우, val이 root의 왼쪽에 있을 가능성이 높으므로 left subtree로 이동
  • val이 root->val보다 클 경우, val이 root의 오른쪽에 있을 가능성이 높으므로 right subtree로 이동

 

/**
 * 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* searchBST(TreeNode* root, int val) {
        if (root == NULL) return NULL; //끝까지 search 했는데도 찾지 못 했을 경우
        if (val == root->val) return root; // val 값을 가진 노드를 찾았을 경우
        else if (val < root->val) return searchBST(root->left, val); // val이 root의 왼쪽에 있을 가능성이 높으므로 left subtree로 이동
        else return searchBST(root->right, val); // val이 root의 오른쪽에 있을 가능성이 높으므로 right subtree로 이동
    }
};