力扣700 二叉搜索树中的搜索

标签：return val root 力扣 搜索 searchBST null 树中 left

题目：

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

示例：

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

思路：

　　二叉搜索树是一个有序树：

（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）它的左、右子树也分别为二叉搜索树

　　递归上，单层逻辑：

　　二叉搜索树的节点是有序的，所以可以有方向的去搜索。如果root->val > val，搜索左子树，如果root->val < val，就搜索右子树，最后如果都没有搜索到，就返回NULL。

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
       if(root==null||root.val==val){
            return root;
        }
        if (val<root.val) {//利用搜索树的有序
            return searchBST(root.left, val);
        } else {
            return searchBST(root.right, val);
        }
    }
}

如果是搜索普通二叉树：

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
       if(root==null||root.val==val){
            return root;
        }
        //这里不用多此一举检查root.left!=null,空的话递归的时候就会返回null
        TreeNode left = searchBST(root.left, val);
        if (left != null) {
            return left;
        }
        return searchBST(root.right, val);
    }
}

 写题时候的错误：多次递归，超出时间限制

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
       if(root==null||root.val==val){
            return root;
        }
        //这里不用多此一举检查root.left!=null,空的话递归的时候就会返回null
        if (searchBST(root.left, val) != null) {//多次调用
            return searchBST(root.left, val);
        }
        return searchBST(root.right, val);
    }
}

 

标签：return,val,root,力扣,搜索,searchBST,null,树中,left
From： https://www.cnblogs.com/cjhtxdy/p/17090197.html