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 删除二叉搜索树中的节点

在删除待删除节点时有如下五种情况

1. 没找到待删除节点，遍历到空节点后返回
2. 待删除节点左右节点都为空，删除后直接返回空
3. 待删除节点左节点为空，右节点不为空，删除节点后让右孩子作为根节点
4. 待删除节点右节点为空，左节点不为空，删除节点后让左孩子作为根节点
5. 待删除节点左右节点都不为空，将待删除节点的左孩子放到右孩子的最左节点的左孩子处，返回待删除节点的右孩子作为根节点

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)