今日刷题3道:235. 二叉搜索树的最近公共祖先,701.二叉搜索树中的插入操作, 450.删除二叉搜索树中的节点
● 235. 二叉搜索树的最近公共祖先
视频讲解:https://www.bilibili.com/video/BV1Zt4y1F7ww
递归法:
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root==NULL) return root; if(root->val > p->val && root->val > q->val){ TreeNode* result = lowestCommonAncestor(root->left, p, q); if(root->left!=NULL) return result; } if(root->val < p->val && root->val < q->val){ TreeNode* result = lowestCommonAncestor(root->right, p, q); if(root->right!=NULL) return result; } return root; } }; 迭代法:class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while(root) {
if (root->val > p->val && root->val > q->val) {
root = root->left;
} else if (root->val < p->val && root->val < q->val) {
root = root->right;
} else return root;
}
return NULL;
}
};
● 701.二叉搜索树中的插入操作
视频讲解:https://www.bilibili.com/video/BV1Et4y1c78Y
class Solution { public: TreeNode* insertIntoBST(TreeNode* root, int val) { if(root == NULL){ TreeNode* node = new TreeNode(val); return node; } if(root->val > val) root->left = insertIntoBST(root->left,val); if(root->val < val) root->right = insertIntoBST(root->right,val); return root; } };● 450.删除二叉搜索树中的节点
视频讲解:https://www.bilibili.com/video/BV1tP41177us
class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { if(root == nullptr) return root; if(root->val==key){ if(root->left==nullptr && root->right==nullptr){ delete root; return nullptr; } else if(root->left == nullptr){ auto resnode = root->right; delete root; return resnode; } else if(root->right == nullptr){ auto resnode = root->left; delete root; return resnode; } else{ TreeNode* cur = root->right; while(cur->left!=nullptr){ cur=cur->left; } cur->left=root->left; TreeNode* tmp = root; root = root->right; delete tmp; return root; } } if(root->val > key) root->left = deleteNode(root->left, key); if(root->val< key) root->right = deleteNode(root->right, key); return root; } }; 标签:right,TreeNode,22,val,训练营,随想录,return,root,left From: https://www.cnblogs.com/zzw0612/p/17060195.html