石家庄的网站建设公司哪家好,手机手机网站制作,erp仓库管理系统,设计集团有限公司题目 给定二叉搜索树#xff08;BST#xff09;的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在#xff0c;则返回 NULL。
例如#xff0c; 在上述示例中#xff0c;如果要找的值是 5#xff0c;但因为没有节点…题目 给定二叉搜索树BST的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在则返回 NULL。
例如 在上述示例中如果要找的值是 5但因为没有节点值为 5我们应该返回 NULL。
思路
之前我们讲的都是普通二叉树那么接下来看看二叉搜索树。
大家可以参考这个博客加深对二叉搜索树的理解数据结构——二叉搜索树详解-CSDN博客
二叉搜索树是一个有序树 若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉搜索树 这就决定了二叉搜索树递归遍历和迭代遍历和普通二叉树都不一样。
本题其实就是在二叉搜索树中搜索一个节点。那么我们来看看应该如何遍历。
递归法 1、确定递归函数的参数和返回值
递归函数的参数传入的就是根节点和要搜索的数值返回的就是以这个搜索数值所在的节点。
TreeNode* searchBST(TreeNode* root, int val) 2、确定终止条件
如果root为空或者找到这个数值了就返回root节点。
if (root NULL || root-val val) return root; 3、确定单层递归的逻辑
看看二叉搜索树的单层递归逻辑有何不同。
因为二叉搜索树的节点是有序的所以可以有方向的去搜索。
如果root-val val搜索左子树如果root-val val就搜索右子树最后如果都没有搜索到就返回NULL。
代码如下
TreeNode* result NULL;
if (root-val val) result searchBST(root-left, val);
if (root-val val) result searchBST(root-right, val);
return result;
递归函数的返回值是什么? 是 左子树如果搜索到了val要将该节点返回。 如果不用一个变量将其接住那么返回值不就没了。
所以要 result searchBST(root-left, val)。
整体代码如下
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if (root NULL || root-val val) return root;TreeNode* result NULL;if (root-val val) result searchBST(root-left, val);if (root-val val) result searchBST(root-right, val);return result;}
};
或者我们也可以这么写
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if (root NULL || root-val val) return root;if (root-val val) return searchBST(root-left, val);if (root-val val) return searchBST(root-right, val);return NULL;}
};
迭代法
一提到二叉树遍历的迭代法可能立刻想起使用栈来模拟深度遍历使用队列来模拟广度遍历。
对于二叉搜索树可就不一样了因为二叉搜索树的特殊性也就是节点的有序性可以不使用辅助栈或者队列就可以写出迭代法。
对于一般二叉树递归过程中还有回溯的过程例如走一个左方向的分支走到头了那么要调头在走右分支。
而对于二叉搜索树不需要回溯的过程因为节点的有序性就帮我们确定了搜索的方向。
例如要搜索元素为3的节点我们不需要搜索其他节点也不需要做回溯查找的路径已经规划好了。
中间节点如果大于3就向左走如果小于3就向右走如图 所以迭代法代码如下
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;}
};
