本文主要是介绍算法训练营第二十四天 | LeetCode 235 二叉搜索树的最近公共祖先、，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
LeetCode 235 二叉搜索树的最近公共祖先
这题可以不用递归，直接迭代即可。若初始情况下根节点就是p或者q或者空直接返回即可。这里刚好是二叉搜索树，而且每个值都唯一，可用值比较来确定位置，避免用指针了。
情况有以下四种：如果p节点和q节点值都小于当前节点，说明都在左子树，当前指针移到左子树；如果p节点指针和q节点指针都大于当前节点，说明都在右子树，当前指针移到右子树；如果p节点指针和q节点指针刚好一个大于一个小于当前节点，说明刚好找到了最近的公共祖先，直接退出循环；如果其中一个出现了最初的某一个等于root的情况，也直接退出循环。
这里需要注意的是一个大于一个小于要分情况，不能用乘法简化，测试用例中有很大的数，会溢出。
代码如下：
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == nullptr || root->val == p->val || root->val == q->val) {return root;}while (root) {if (p->val < root->val && q->val < root->val) {root = root->left;}if (p->val > root->val && q->val > root->val) {root = root->right;}if (p->val < root->val && q->val > root->val) {break;}if (p->val > root->val && q->val < root->val) {break;}if (p->val == root->val || q->val == root->val) {break;}}return root;}
};改进后如下：
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == nullptr || root->val == p->val || root->val == q->val) {return root;}TreeNode* cur = root;while (cur) {if (p->val < cur->val && q->val < cur->val) {cur = cur->left;}if (p->val > cur->val && q->val > cur->val) {cur = cur->right;}if (p->val < cur->val && q->val > cur->val) {break;}if (p->val > cur->val && q->val < cur->val) {break;}if (p->val == cur->val || q->val == cur->val) {break;}}return cur;}
};LeetCode 701 二叉搜索树中的插入操作
一开始就想到用迭代，当然递归也可以。不过刚开始时只顾着迭代比较，没有留意到子树右下角还有可能会有更大的值，所以用双指针prev和cur比较时其实是不能满足于在中途就停止的。需要把节点都放到最底层叶子节点处结算，结合二叉搜索树性质可以想到这样其实并没有违背规则。当然其实这题比较绕，感觉面试不大可能会被拿出来，这里权当练练手了。
简单来说思路就是双指针+迭代。如果cur的值大于val，说明应该插入到左子树，将cur赋给prev，cur左移，否则cur右移直到到达底层，这时候判断prev值和val哪个大，来决定插入到左叶子还是右叶子就行了。
另外需要注意根节点是否为空，迭代时不一定能注意到。
代码如下：
class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {TreeNode* prev = root;TreeNode* cur = root;TreeNode* newNode = new TreeNode(val);if (!root) return newNode;while (cur) {if (cur->val < val) {prev = cur;cur = cur->right;}else if (cur->val > val) {prev = cur;cur = cur->left;}}if (prev->val < val) prev->right = newNode;else prev->left = newNode;return root;}
};LeetCode 450 删除二叉树中的节点
这题首先我们还是要用到双指针法，具体思路和上题差不多，但是最后我们要对目标节点依据子节点数量进行分类讨论：无子结点、有左子节点、有右子节点、两个子节点都有。对应的处理措施前三种情况下比较简单，直接双指针删除链表操作即可。后一种需要再用一个指针遍历到右子节点最左下角的子节点，将其指向cur的左子节点，然后将prev flag（0表示左，1表示右，循环过程中随时更新）方向的指针指向cur右子节点即可。
还要注意处理root本身就是要删除节点的情况，这里要借鉴下链表中的虚拟头节点的思想，可以很好地解决这个问题。
代码如下：
class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if (!root) return nullptr;TreeNode* virtualHead = new TreeNode(0);virtualHead->left = root;TreeNode* prev = virtualHead;TreeNode* cur = root;int flag = 0;while (cur && cur->val != key) {if (cur->val > key) {prev = cur;cur = cur->left;flag = 0;}else if (cur->val < key) {prev = cur;cur = cur->right;flag = 1;}}if (!cur) return virtualHead->left;if (!cur->left && !cur->right) {if (flag) prev->right = nullptr;else prev->left = nullptr;return virtualHead->left; } if (!cur->left) {if (flag) prev->right = cur->right;else prev->left = cur->right;return virtualHead->left;}if (!cur->right) {if (flag) prev->right = cur->left;else prev->left = cur->left;return virtualHead->left;}TreeNode* temp = cur->right;while (temp && temp->left) temp = temp->left;temp->left = cur->left;if (flag) prev->right = cur->right;else prev->left = cur->right;return virtualHead->left;}
};时间复杂度在O(h)以内，满足进阶要求。
这篇关于算法训练营第二十四天 | LeetCode 235 二叉搜索树的最近公共祖先、的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
