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

问题

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

例如
给定二叉搜索树:

    4<br />       / \<br />      2   7<br />     / \<br />    1   3

和值: 2
你应该返回如下子树:
2
/ \
1 3
在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 null

思路

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

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉搜索树

这就决定了，二叉搜索树，递归遍历和迭代遍历和普通二叉树都不一样

解法一：递归

• 确定递归的参数和返回值

  • 递归函数的参数传入的是根节点和要搜索的值，返回的就是以这个搜索数值所在的节点

    TreeNode searchBST(TreeNode root, int val)
    

• 确定终止条件

  • 如果root为空或者找到这个数值，就返回root节点

    if(root == null || root.val == val)
    return root;
    

• 确定单层递归的逻辑

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

    if (root.val > val) 
    return searchBST(root.left, val); // 注意这里加了return 
    if (root.val < val) 
    return searchBST(root.right, val);
    return null;
    

    搜索到目标节点了，就要立即return，这样才是找到节点就返回（搜索某一条边），如果不加return，就是遍历整棵树了

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

解法二：迭代法

一提到二叉树遍历的迭代法，可能立刻想起使用栈来模拟深度遍历，使用队列来模拟广度遍历

对于二叉搜索树可就不一样了，因为二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法

对于一般二叉树，递归过程中还有回溯的过程，例如走一个左方向的分支走到头了，那么要调头，在走右分支

而对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向

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