package 二叉树.二叉搜索树;
/**
 * https://leetcode-cn.com/problems/search-in-a-binary-search-tree/
 * @author Huangyujun
 *
 *从自己的代码书写得到一个提示：有返回值的递归函数，需要用变量接收返回值 【对应的变量】
 */
public class _700_二叉搜索树中的搜索 {
    //递归实现：① 若是值 = 根值，直接返回根结点；② 若是值 > 根值，只能到右子树中找，否则只能在左子树中找。
    class Solution {
          public TreeNode searchBST(TreeNode root, int val) {
            if (root == null || val == root.val) return root;
            return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
          }
        }
//接下来的代码实现思路与官网一致，就是写得有点啰嗦了
    //多看看官网的代码思路：
    //尤其是最后一句：结果要么是在A要么是在B，就return（条件偏向A）？ A ：B; 
//    public TreeNode searchBST(TreeNode root, int val) {
//        //找到返回即可
//        if(root == null || val == root.val)    return root;
//        if(root.val > val) {
//            //当前值小于，在右子树找
//            root =  searchBST(root.left,val); 
//        }else if(root.val < val) {
//            //大了，左子树找
//            root = searchBST(root.right,val); 
//        }
//        
//        return root;
//    }
    //迭代实现：当一直不是 根值时，判断若 值小于根值，则只能在左区域找，否则只能在右区域找
    class Solution2 {
          public TreeNode searchBST(TreeNode root, int val) {
            while (root != null && val != root.val)
              root = val < root.val ? root.left : root.right;
            return root;
          }
        }
}