做公司网站 烟台,wordpress需要配置文件,wordpress响应式视频,网站开发实践报告递归法 确定递归函数的参数和返回值 递归函数的参数传入的就是根节点和要搜索的数值#xff0c;返回的就是以这个搜索数值所在的节点。
代码如下#xff1a; public TreeNode searchBST(TreeNode root, int val)
确定终止条件 如果root为空#xff0c;返回null#xff0c…
递归法 确定递归函数的参数和返回值 递归函数的参数传入的就是根节点和要搜索的数值返回的就是以这个搜索数值所在的节点。
代码如下 public TreeNode searchBST(TreeNode root, int val)
确定终止条件 如果root为空返回null找到这个数值了就返回root节点。
if(rootnull) return null;
if(root.valval){return root;
}
确定单层递归的逻辑 看看二叉搜索树的单层递归逻辑有何不同。
因为二叉搜索树的节点是有序的所以可以有方向的去搜索。
如果root.val val搜索左子树如果root.val val就搜索右子树最后如果都没有搜索到就返回NULL。
代码如下
if(valroot.val){return searchBST(root.left,val);
}
if(valroot.val){return searchBST(root.right,val);
}
return null;
迭代法 一提到二叉树遍历的迭代法可能立刻想起使用栈来模拟深度遍历使用队列来模拟广度遍历。
对于二叉搜索树可就不一样了因为二叉搜索树的特殊性也就是节点的有序性可以不使用辅助栈或者队列就可以写出迭代法。
对于一般二叉树递归过程中还有回溯的过程例如走一个左方向的分支走到头了那么要调头在走右分支。
而对于二叉搜索树不需要回溯的过程因为节点的有序性就帮我们确定了搜索的方向。
例如要搜索元素为3的节点我们不需要搜索其他节点也不需要做回溯查找的路径已经规划好了。
class Solution {public TreeNode searchBST(TreeNode root, int val) {while(root!null){if(root.valval) return root;else if(valroot.val) rootroot.left;else rootroot.right;}return null;}
}
