做关于手机的网站 该如何设计,mvc 网站模板,wordpress链接速度慢,蒙阴蜜桃难度参考 难度#xff1a;中等 分类#xff1a;二叉树 难度与分类由我所参与的培训课程提供#xff0c;但需要注意的是#xff0c;难度与分类仅供参考。且所在课程未提供测试平台#xff0c;故实现代码主要为自行测试的那种#xff0c;以下内容均为个人笔记#xff0c;旨…难度参考 难度中等 分类二叉树 难度与分类由我所参与的培训课程提供但需要注意的是难度与分类仅供参考。且所在课程未提供测试平台故实现代码主要为自行测试的那种以下内容均为个人笔记旨在督促自己认真学习。
题目 给定二叉搜索树(BST)的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在则返回NULL. 示例1: 输入root[4,2,7,1,3],val2 输出[2,1,3] 示例2: 输入root[4,2,7,1,3],val5 输出[] 提示 树中节点数在[1,5000]范围内 1Node.Va110(7) root是二叉搜索树 1val10(7) 额外 希望你可以尝试使用迭代法尤其要考虑二叉搜索树的特性来优化迭代。
思路 这个问题要求在一个二叉搜索树中查找一个特定值的节点并且返回以这个节点为根的子树。如果找不到这个值则返回NULL。由于这是一个二叉搜索树我们可以利用其特性来指导搜索过程使之比一般的二叉树更高效。在二叉搜索树中对于任何节点其左子树中的所有节点都小于这个节点而右子树中的所有节点都大于这个节点。 基于这个性质我们可以使用如下思路来进行查找
从树的根节点开始搜索。比较当前节点的值与目标值 如果当前节点的值等于目标值那么我们找到了目标节点返回这个节点即可。如果目标值小于当前节点的值那么我们应该在左子树中继续搜索。如果目标值大于当前节点的值那么我们应该在右子树中继续搜索。如果当前节点是NULL表示我们已经到达了叶子节点但未找到目标值此时应该返回NULL。重复以上步骤直到找到目标值或遍历到了叶子节点。
示例 假设我们有如下的二叉搜索树结构 4/ \2 7/ \1 3现在让我们分两个示例来查找值为2的节点。 示例一查找值为2的节点
我们从根节点开始也就是值为4的节点。因为2小于4我们向左子树移动。现在我们在值为2的节点。我们比较当前节点的值(2)与目标值(2)发现它们相等。我们找到了目标节点并返回这个节点。 函数返回包含值为2的子树的根也就是 2/ \1 3示例二查找值为5的节点
我们从根节点开始也就是值为4的节点。因为5大于4我们向右子树移动。现在我们在值为7的节点。因为5小于7我们向左子树移动。在值为7的节点处并没有左子节点所以我们到达了NULL。我们没有找到目标节点返回NULL。
梳理 这样的实现能够工作因为它依赖于二叉搜索树Binary Search Tree, BST的基本性质。在二叉搜索树中每个节点都满足以下条件
节点的左子树中的每个节点的值都小于当前节点的值。节点的右子树中的每个节点的值都大于当前节点的值。左子树和右子树也分别是二叉搜索树。 这个性质允许我们使用二分查找的方法快速地在树中定位一个值是否存在。具体到 searchBST 函数中的实现
开始查找我们从根节点开始查找。比较值我们将目标值与当前节点的值进行比较。 如果目标值与当前节点的值相等我们就找到了需要的节点返回它如果目标值小于当前节点的值根据二叉搜索树的性质我们知道目标值如果存在于树中必定在当前节点的左子树中。因此我们更新当前节点为其左子节点继续查找如果目标值大于当前节点的值那么目标值同样如果存在一定在当前节点的右子树中。因此我们更新当前节点为其右子节点继续查找。终止条件这个过程会一直进行直到当前节点为空这意味着目标值不存在于树中返回 nullptr或者找到了一个节点的值等于目标值返回该节点。 代码
#include iostream // 包含标准输入输出流的库using namespace std; // 使用命名空间std省去std::前缀struct TreeNode { // 定义二叉树节点结构int val; // 节点存储的值TreeNode *left; // 指向左子树的指针TreeNode *right; // 指向右子树的指针TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 初始化构造函数nullptr表示空指针
};TreeNode* searchBST(TreeNode* root, int val) { // 定义搜索二叉搜索树的函数while (root ! nullptr root-val ! val) { // 当树不为空且当前节点值不等于目标值时root val root-val ? root-left : root-right; // 判断目标值是在左子树还是右子树}return root; // 返回找到的节点指针如果没找到则是nullptr
}int main() { // 主函数TreeNode* root new TreeNode(4); // 创建根节点赋值为4root-left new TreeNode(2); // 创建根的左子节点赋值为2root-right new TreeNode(7); // 创建根的右子节点赋值为7root-left-left new TreeNode(1); // 创建左子节点的左子节点赋值为1root-left-right new TreeNode(3); // 创建左子节点的右子节点赋值为3int search_val 2; // 设置要查找的值为2TreeNode* result searchBST(root, search_val); // 调用搜索函数if (result ! nullptr) { // 如果搜索结果不为空cout 搜索到节点值为 search_val 的节点是 result-val endl;if (result-left ! nullptr) // 如果搜索到的节点的左子树不为空cout 左子节点 result-left-val endl; // 打印左子节点的值if (result-right ! nullptr) // 如果搜索到的节点的右子树不为空cout 右子节点 result-right-val endl; // 打印右子节点的值} else { // 如果搜索结果为空cout 未找到节点值为 search_val 的节点 endl; // 表明没找到节点}search_val 5; // 设置要查找的值为5result searchBST(root, search_val); // 再次调用搜索函数if (result ! nullptr) { // 如果搜索结果不为空cout 搜索到节点值为 search_val 的节点是 result-val endl;if (result-left ! nullptr) // 如果搜索到的节点的左子树不为空cout 左子节点 result-left-val endl;if (result-right ! nullptr) // 如果搜索到的节点的右子树不为空cout 右子节点 result-right-val endl;} else { // 如果搜索结果为空cout 未找到节点值为 search_val 的节点 endl; // 表明没找到节点}// 释放动态分配的内存没写懒return 0; // 主函数结束返回0
} 时间复杂度O(n) 空间复杂度O(n)
打卡
