# LeetCode Easy 700. Search in a Binary Search Tree

tags: leetcode

問題

• Explore
• Problems

アイデア

valを持つノードのポインタを返せという問題です．見つからない場合はNULLを返します．

再帰的探索すれば良いです．

解法

• base case
  • 現在のノードのみを見て，そのノードの保持する値がvalと同じなら，そのノードを返します．
  • 全て違う場合はNULLを返します．
• recursive step
  • 保持する値がvalより大きい時は，小さい値を保持するノード，つまり左部分木に向かいます．
  • 小さい時は，大きい値を保持するノード，つまり右部分木に向かいます．

計算量

ノードの数を$N$，木の深さを$h$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(h)$

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  TreeNode* searchBST(TreeNode* root, int val) {
    if (root->val == val)
      return root;
    
    if (root->val > val && root->left)
      return searchBST(root->left, val);
    if (root->val < val && root->right)
      return searchBST(root->right, val);
    
    return NULL;
  }
};