LeetCode #700 Search in a Binary Search Tree

問題概要

入力値：root(BST), val(int)
出力値：root
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.
問題のリンク

入力例

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

解答例1

計算量：O(n)
Recursion
Python

class Solution(object):
    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        if not root:
            return
        if root.val == val:
            return root
        if root.val < val:
            return self.searchBST(root.right, val)
        else:
            return self.searchBST(root.left, val)

Runtime: 41ms
Beats: 95.58%

C++

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr) {
            return nullptr;
        }
        if (root->val == val) {
            return root;
        }
        if (root->val < val) {
            return searchBST(root->right, val);
        } else {
            return searchBST(root->left, val);
        }
    }
};

Runtime: 19ms
Beats: 98.50%