只是你走得好快，不回头看看我们一起走过的路吗
—— 24.11.2
700. 二叉搜索树中的搜索
给定二叉搜索树（BST）的根节点
root和一个整数值val。你需要在 BST 中找到节点值等于
val的节点。 返回以该节点为根的子树。 如果节点不存在，则返回null。示例 1:
输入：root = [4,2,7,1,3], val = 2 输出：[2,1,3]
示例 2：
输入：root = [4,2,7,1,3], val = 5
输出：[]
方法1 非递归寻找
思路
由于二叉搜索树的特性为左孩子的key值小于根节点的key值，根节点的key值小于右孩子的key值，根据传入的key值与根节点的key值相比，一层层不断循环迭代，找到最终结果
/*** 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) {while(root != null){if(root.val > val){root = root.left;}else if(root.val < val){root = root.right;}else{return root;} }return null;}
}
方法2 递归寻找
思路
由于二叉搜索树的特性为左孩子的key值小于根节点的key值，根节点的key值小于右孩子的key值，根据传入的key值与根节点的key值相比，一层层不断递归，若是root的key值小于传入的key值，则说明应该在root的右子树部分，将root更新为root.right，反之，则更新为root.left
/*** 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.left,val);}else if(root.val < val){return searchBST(root.right,val);}else{return root;} }
}