二叉树:二叉搜索树登场
利用好二叉搜索树的特性 , 就发现遍历都简单了
700.二叉搜索树中的搜索给定二叉搜索树(BST)的根节点和一个值 。 你需要在BST中找到节点值等于给定值的节点 。 返回以该节点为根的子树 。 如果节点不存在 , 则返回 NULL 。
例如 ,
文章插图
在上述示例中 , 如果要找的值是 5 , 但因为没有节点值为 5 , 我们应该返回 NULL 。
思路之前我们讲了都是普通二叉树 , 那么接下来看看二叉搜索树 。
在关于二叉树 , 你该了解这些!中 , 我们已经讲过了二叉搜索树 。
二叉搜索树是一个有序树:
- 若它的左子树不空 , 则左子树上所有结点的值均小于它的根结点的值;
- 若它的右子树不空 , 则右子树上所有结点的值均大于它的根结点的值;
- 它的左、右子树也分别为二叉搜索树
本题 , 其实就是在二叉搜索树中搜索一个节点 。 那么我们来看看应该如何遍历 。
递归法
- 确定递归函数的参数和返回值
代码如下:
TreeNode* searchBST(TreeNode* root, int val)
- 确定终止条件
if (root == NULL || root->val == val) return root;
- 确定单层递归的逻辑
因为二叉搜索树的节点是有序的 , 所以可以有方向的去搜索 。
【二叉树:二叉搜索树登场】如果root->val > val , 搜索左子树 , 如果root->val < val , 就搜索右子树 , 最后如果都没有搜索到 , 就返回NULL 。
代码如下:
if (root->val > val) return searchBST(root->left, val); // 注意这里加了return if (root->val < val) return searchBST(root->right, val);return NULL;
这里可能会疑惑 , 在递归遍历的时候 , 什么时候直接return 递归函数的返回值 , 什么时候不用加这个 return呢 。我们在二叉树:递归函数究竟什么时候需要返回值 , 什么时候不要返回值? 中讲了 , 如果要搜索一条边 , 递归函数就要加返回值 , 这里也是一样的道理 。
「因为搜索到目标节点了 , 就要立即return了 , 这样才是找到节点就返回(搜索某一条边) , 如果不加return , 就是遍历整棵树了 。 」
整体代码如下:
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就向右走 , 如图:
推荐阅读
- R9 5900H即将登场,机械革命发布AMD旗舰游戏本
- 别着急抢小米11,荣耀V40将登场,颜值比肩华为Mate40
- 当下正流行,轻量化无线游戏鼠标代表作登场!赛睿Aerox 3 Wireless体验
- 让花粉失望了,2021首款鸿蒙产品登场,并不是华为P50
- Apple Fitness+播放列表现可在Apple Music搜索上找到
- 小米预告片暗示新机即将登场:POCO F2来袭
- 小米11发布之后,第五款5nm芯片也正式登场,却遭受用户质疑
- 美媒:2020年个人技术装备有亮点也有黑点 在线聊天在线健身电动单车火热登场
- vivo X60正式登场,全球首发三星5nm处理器
- MIUI 12.5亮相!首个“跨界”作品登场还有新超级壁纸