leetcode-700.二叉搜索树中的搜索

题目链接

700. 二叉搜索树的搜索

代码

1. 递归

   class Solution {
       public TreeNode searchBST(TreeNode root, int val) {
           if (root == null || root.val == val) {
               return root;
           } else if (root.val > val) {
               return searchBST(root.left, val);
           } else {
               return searchBST(root.right, val);
           }
       }
   }

2. 迭代

   class Solution {
       public TreeNode searchBST(TreeNode root, int val) {
           TreeNode node = root;
           while (node != null && node.val != val) {
               node = node.val > val ? node.left : node.right;
           }
           return node;
       }
   }

复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(1)