LeetCode/700. 二叉搜索树中的搜索

700. 二叉搜索树中的搜索

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

例如，

输入: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

你应该返回如下子树：

  2     
 / \   
1   3

在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题根据二叉搜索树的特性，可知根节点的左孩子都小于它本身，根节点的右孩子都大于它本身，我们递归进行比较，如果能找到返回子树，如果找不到返回null

具体代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode result = null;

    public TreeNode searchBST(TreeNode root, int val) {
        search(root, val);
        return result;
    }

    void search(TreeNode node, int target) {
        if (node == null) return;
        if (target == node.val) {
            result = node;
            return;
        }
        if (target > node.val) searchBST(node.right, target);
        if (target < node.val) searchBST(node.left, target);
    }
}

简洁版本：

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