[Leetcode] 700. Search in a Binary Search Tree 문제 풀이

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

Search in a Binary Search Tree - LeetCode

문제 내용

바이너리 서치 트리가 주어지는 데 val이랑 같은 값을 가진 노드 출력

 

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

 

Constraints:

• The number of nodes in the tree is in the range [1, 5000].
• 1 <= Node.val <= 10^7
• root is a binary search tree.
• 1 <= val <= 10^7

문제 풀이

바이너리 서치 특징으로 부모노드 보다 크면 오른쪽 작으면 왼쪽으로 정렬된다.

그래서 부모 노드 값을 비교해보고 오른쪽으로 갈지 왼쪽으로 갈지 정하면 된다.

 

코드

/**
 * 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 == nullptr)
            return nullptr;
        
        if (root->val == val)
            return root;
        
        return (root->val < val) ? searchBST(root->right, val) : searchBST(root->left, val);
    }
};