网站内容的作用,单位门户网站建设方案,在线制作电子公章生成器,app下载官方免费下载235. 二叉搜索树的最近公共祖先
1. LeetCode链接
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
2. 题目描述 3. 解法
利用二叉搜索树的特性进行公共节点的判断#xff1a;
1. 此节点为公共节点#xff1a;p、q恰好在此节点的左右棵子树上。即…235. 二叉搜索树的最近公共祖先
1. LeetCode链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
2. 题目描述 3. 解法
利用二叉搜索树的特性进行公共节点的判断
1. 此节点为公共节点p、q恰好在此节点的左右棵子树上。即root的val在p、q的val所构成的闭区间内。
2. 如果p、q的val恰好都大于root的val则只需要考虑root-right
3. 如果p、q都小于root则只考虑root-left
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root NULL) return NULL;if (root-val p-val root-val q-val || root-val p-val root-val q-val) return root;else if (p-val root-val q-val root-val) return lowestCommonAncestor(root-right, p, q);else return lowestCommonAncestor(root-left, p, q);}
};
更精简一点
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (p-val root-val q-val root-val) return lowestCommonAncestor(root-right, p, q);else if (p-val root-val q-val root-val) return lowestCommonAncestor(root-left, p, q);else return root;}
};
迭代法
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {queueTreeNode* qu;qu.push(root);TreeNode* cur;while (!qu.empty()) {cur qu.front();qu.pop();if (q-val cur-val p-val cur-val) qu.push(cur-left);else if (q-val cur-val p-val cur-val) qu.push(cur-right);else break;}return cur;}
};
更加精简的
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. 二叉搜索树中的插入操作
1. LeetCode链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
2. 题目描述 3. 解法
先在二叉搜索树中查询val直到找到NULL然后将val插入该NULL。
迭代
class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {TreeNode* a new TreeNode(val);if (root NULL) return a;TreeNode* cur root;while (cur) {if (cur-val val cur-left ! NULL) cur cur-left;else if (cur-val val cur-left NULL) {cur-left a;break;}else if (cur-val val cur-right ! NULL) cur cur-right;else {cur-right a;break;}}return root;}
};
递归。相当于将在遍历至NULL的路上重新连接原本的树直到遇到NULL然后把NULL换成val。
1. 参数和返回值。参数当前节点和val。返回值当前节点。
2. 终止条件。遇到NULL且将NULL替换为val。
3. 比较root和val确定从左子树走还是右子树走root-left root-left / root-right root-right;
class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if (root NULL) {TreeNode* n new TreeNode(val);return n;}if (root-val val) root-left insertIntoBST(root-left, val);if (root-val val) root-right insertIntoBST(root-right, val);return root;}
};
450. 删除二叉搜索树中的节点
1. LeetCode链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
2. 题目描述 3. 解法
删除节点后需要考虑是让左子树上位还是右子树上位。这道题的话无所谓暂且让左子树上位吧。这个时候问题来了右子树该如何安排?
其实这道题目可以看成左子树上位后将右子树插入左子树因为两边都是二叉搜索树且左子树必小于右子树所以只要简单插入即可。
class Solution {
public:TreeNode* insertNode(TreeNode* root, TreeNode* key) {if (root NULL) return key;if (key NULL) return root;if (key-val root-val) root-right insertNode(root-right, key);if (key-val root-val) root-left insertNode(root-left, key);return root;}TreeNode* deleteNode(TreeNode* root, int key) {if (root NULL) return NULL;if (root-val key) {TreeNode* left root-left;TreeNode* right root-right;delete root;return insertNode(left, right);}if (key root-val) root-right deleteNode(root-right, key);if (key root-val) root-left deleteNode(root-left, key);return root;}
};
细想的话其实如果将左子树上位右子树一定被插在左子树中的最右节点的右节点上如果让右子树上位左子树一定被插在最左节点的左节点上。
class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if (root NULL) return NULL;if (root-val key) {TreeNode* left root-left;TreeNode* right root-right;delete root;if (left NULL) return right;if (right NULL) return left;TreeNode* cur left;while (left ! NULL left-right ! NULL) left left-right;left-right right;return cur;}if (key root-val) root-right deleteNode(root-right, key);if (key root-val) root-left deleteNode(root-left, key);return root;}
};
更巧妙的是删除当前节点后最合适的候选节点是左子树最右节点或者右子树最左节点。可以通过交换val值将root换到底部然后再遇到root后直接删除。
class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if (root nullptr) return root;if (root-val key) {if (root-right nullptr) { // 这里第二次操作目标值最终删除的作用return root-left;}TreeNode *cur root-right;while (cur-left) {cur cur-left;}swap(root-val, cur-val); // 这里第一次操作目标值交换目标值其右子树最左面节点。}root-left deleteNode(root-left, key);root-right deleteNode(root-right, key);return root;}
};
