LeetCode75| 二叉搜索树
目录
700 二叉搜索树中的搜索
迭代
递归
450 删除二叉搜索树中的节点
700 二叉搜索树中的搜索
注意二叉搜索树的性质即可
迭代
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {while(root != NULL){if(root->val < val)root = root->right;else if(root->val > val)root = root->left;else return root;}return NULL;}
};时间复杂度O(n)
空间复杂度O(n)
递归
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(root == NULL)return NULL;if(root->val == val)return root;return root->val > val?searchBST(root->left,val) : searchBST(root->right,val); }
};时间复杂度O(n)
空间复杂度O(1)
450 删除二叉搜索树中的节点
在删除待删除节点时有如下五种情况
- 没找到待删除节点，遍历到空节点后返回
- 待删除节点左右节点都为空，删除后直接返回空
- 待删除节点左节点为空，右节点不为空，删除节点后让右孩子作为根节点
- 待删除节点右节点为空，左节点不为空，删除节点后让左孩子作为根节点
- 待删除节点左右节点都不为空，将待删除节点的左孩子放到右孩子的最左节点的左孩子处，返回待删除节点的右孩子作为根节点
class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if(root == NULL)return NULL;//情况一if(root->val == key){if(root->left == NULL && root->right == NULL)return NULL;//情况二else if(root->left == NULL && root->right != NULL)return root->right;//情况三else if(root->left != NULL && root->right == NULL)return root->left;//情况四else{//情况五TreeNode* cur = root->right;while(cur->left != NULL){cur = cur->left;}cur->left = root->left;return root->right;}}if(root->val > key)root->left = deleteNode(root->left,key);if(root->val < key)root->right = deleteNode(root->right,key);return root;}
};时间复杂度O(n)
空间复杂度O(n)