高端网约车有哪些平台_王爷不可以_新闻最近的新闻_免费推广软件 推广帮手

700. 二叉搜索树中的搜索 - 力扣（LeetCode）

题目

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

示例 1:

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

示例 2:

输入：root = [4,2,7,1,3], val = 5
输出：[]

提示：

• 树中节点数在 [1, 5000] 范围内
• 1 <= Node.val <= 107
• root 是二叉搜索树
• 1 <= val <= 107

思路

1. 根据二叉搜索树的性质进行迭代：若根节点大于val，则搜索左子树；若根节点小于val，则搜索右子树。若找不到，返回nullptr，找到则直接返回。

代码实现

/*** 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) return nullptr;TreeNode* node = root;while(node != nullptr) {if(node->val < val) node = node->right;else if(node->val > val) node = node->left;else return node;}return nullptr;}
};

复杂度分析

• 时间复杂度：根据二叉搜索树的性质，平均时间复杂度应为O(logn)，最坏时间复杂度为O(n)。
• 空间复杂度：O(1)。

知识积累

• 二叉搜索树：左子树小于当前根节点，右子树大于当前根节点。插入、查找、删除的操作的平均时间复杂度都是O(logn)的，但是当树退化成链表时，就会达到最坏的时间复杂度O(n)。
• 为了避免退化的最坏时间复杂度，所以二叉搜索树有其他变体，称为平衡搜索树（红黑树、AVL树等），会尽量保持树的高度在O(logn)的水平。