教育类企业网站杂志社网站建设方案

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

代码如下：

 public TreeNode searchBST(TreeNode root, int val)

确定终止条件 如果root为空，返回null，找到这个数值了，就返回root节点。

if(root==null) return null;
if(root.val==val){return root;
}

确定单层递归的逻辑 看看二叉搜索树的单层递归逻辑有何不同。

因为二叉搜索树的节点是有序的，所以可以有方向的去搜索。

如果root.val > val，搜索左子树，如果root.val < val，就搜索右子树，最后如果都没有搜索到，就返回NULL。

代码如下：

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

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

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

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

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

例如要搜索元素为3的节点，我们不需要搜索其他节点，也不需要做回溯，查找的路径已经规划好了。

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