LeetCode 700：二叉搜索树中的搜索

小半 • 2023年2月3日上午10:53 • 技术随笔 • 阅读 271

方法一：依次遍历

前序遍历，先判断root是否满足，再递归子树；
不需要返回值，使用成员变量r 来记录结果，有则赋给r ，无则遍历结束还是r 还是null


class Solution {
    TreeNode r=null;
    public TreeNode searchBST(TreeNode root, int val) {
        check(root,val);
        return r;
    }

    void check(TreeNode root,int val){
        if(root==null){
            return;
        }
        if(root.val==val){
            r=root;
        }
        check(root.left,val);
        check(root.right,val);
    }   
}

方法二：利用左小右大性质


class Solution {
    TreeNode r=null;
    public TreeNode searchBST(TreeNode root, int val) {
        check(root,val);
        return r;
    }

    void check(TreeNode root,int val){
        if(root==null){
            return;
        }
        if(root.val==val){
            r=root;
        }
        if(val>root.val) check(root.right,val);
        if(val<root.val) check(root.left,val);
    }   
}

或者不用成员变量：


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