LC.700 ｜ 二叉搜索树中的搜索 ｜ 树 ｜ 利用BST有序性

输入：
二叉搜索树的根节点root和一个整数val。

要求：
在 BST 中找到节点值等于val的节点，并返回以该节点为根的子树。如果要找的节点不存在，返回null。

输出：
目标节点的指针TreeNode*。

思路：

二叉搜索树（BST）的核心特性是：左 < 根 < 右。这使得我们在树上的搜索过程类似于二分查找，不需要遍历整棵树。

1. 递归逻辑（主解法）：

   • 终止条件：如果当前节点为空（没找到）或者当前节点值等于目标值（找到了），直接返回当前节点。
   • 利用性质：
     • 如果val < root->val：说明目标在左子树，递归调用searchBST(root->left, val)。
     • 如果val > root->val：说明目标在右子树，递归调用searchBST(root->right, val)。

2. 迭代逻辑（注释写法）：

   • 对于 BST 的搜索，迭代法其实更加高效且直观，因为它不需要维护递归栈。
   • 使用while循环，根据大小关系不断移动root指针指向左孩子或右孩子，直到找到或者root变为null。

复杂度：

• 时间复杂度：O(h) 树高
• 空间复杂度：O(h) 树高

classSolution{public://找到了不必提 直接返回即可//找不到的标准是什么呢 就是右子树的最小节点比你 左子树的最大节点比你小 中间也不等于 这样就是不存在//问题是什么呢 递归查找怎么写...TreeNode*searchBST(TreeNode*root,intval){if(!root){returnnullptr;}if(root->val==val){returnroot;}elseif(root->val>val){returnsearchBST(root->left,val);}else{returnsearchBST(root->right,val);}}/* //while循环写法 while (!isFind) { if (!root) { ans = nullptr; isFind = true; } else if (root->val == val) { ans = root; isFind = true; } else if (root->val > val) { root = root->left; } else { root = root->right; } } */};