二叉搜索树（BST），首先它是个二叉树。
做题之前看了下以前的笔记：
- 【树与二叉树】：https://www.cnblogs.com/pingguo-softwaretesting/p/14587752.html
- 【二叉树的遍历，前序、中序和后序】：https://www.cnblogs.com/pingguo-softwaretesting/p/14615248.html
二叉树（BST）简介
二叉搜索树，又有如下特征：
- 左子树所有节点的元素值均小于根的元素值
- 右子树所有节点的元素值均大于根的元素值
如图所示，图中任何一个节点（比如 4），左边都比它小，右边都比它大。而且任一节点的左右子树仍然是 BST。
题目描述
难度：【简单】
标签：【二叉树】
给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
题目地址：https://leetcode-cn.com/problems/search-in-a-binary-search-tree/
示例
给定二叉搜索树: 4 / \ 2 7 / \ 1 3 和值: 2
你应该返回如下子树:
2 / \ 1 3
如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。
题目大意
就是给一个二叉搜索树，还给了一个目标值，你要从树里找到一个节点的值是等于目标值的，有就返回这个节点的树。
全找完没有，就返回 null。
解题
找节点就是要遍历二叉树的，然后拿这个节点的值与目标值比较，那正常有3种情况：
- 节点值 == 目标值：直接返回这个节点。
- 节点值 < 目标值：根据 BST 的特性，说明左边的树不可能再存在目标值了，应该去右子树中继续寻找。
- 节点值 > 目标值：根据 BST 的特性，说明右边的树不可能再存在目标值了，应该去左子树中继续寻找。
另外异常情况，考虑一个当传入的节点为空，直接返回 null。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode searchBST(TreeNode root, int val) { if (root == null) { return null; } if (root.val < val) { // 比目标值小，应该去右子树中继续寻找 return searchBST(root.right, val); } if (root.val > val) { // 比目标值小，应该去左子树中继续寻找 return searchBST(root.left, val); } return root; } }
