本文主要是介绍180.二叉树:二叉搜索树(力扣),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
代码解决
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/ class Solution { public:TreeNode* searchBST(TreeNode* root, int val) {// 如果根节点为空或者根节点值等于目标值,则返回根节点if(root == nullptr || root->val == val) return root;// 定义一个指针用于存储查找结果,默认为nullptrTreeNode* node = nullptr;// 如果目标值小于根节点值,则在左子树中查找if(val < root->val){node = searchBST(root->left, val);}// 如果目标值大于根节点值,则在右子树中查找else if(val > root->val){node = searchBST(root->right, val);}return node;} };
代码使用了递归的方法。主要思路是首先判断根节点是否为空或者根节点的值是否等于目标值,如果是,则返回根节点。如果目标值小于根节点的值,则在左子树中继续搜索;如果目标值大于根节点的值,则在右子树中继续搜索。
这里简要解释一下代码的工作流程:
- 首先判断根节点是否为空或者根节点的值是否等于目标值,如果是,则返回根节点。
- 定义一个指针
node
用于存储查找结果,默认为nullptr
。- 如果目标值小于根节点的值,则在左子树中继续搜索,即调用
searchBST(root->left, val)
。- 如果目标值大于根节点的值,则在右子树中继续搜索,即调用
searchBST(root->right, val)
。- 返回找到的节点或者
nullptr
。这个算法的时间复杂度是 O(h),其中 h 是树的高度。在最坏的情况下,树是完全不平衡的,时间复杂度为 O(n),其中 n 是树中节点的数量。空间复杂度也是 O(h),因为需要存储递归调用的栈。
这篇关于180.二叉树:二叉搜索树(力扣)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!