跟着Carl学算法--二叉树【3】

力扣链接：二叉树最近公共祖先

题目：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

思路：

截图自灵神题解

事实上如果此题，假设只有这种情况，q，p一定不在一条路径上，那完全可以查找到p，q后，当前结点返回任意非空结点（比如值为1的结点）传达找到信息，一定会有一个root收到左右子树的非空信息，此时返回最近祖先然后一路上传即可（根节点区分左右子树返回的是最近祖先和找到信息即可），返回p或q结点其实就是为了处理这种同一路径的情况，以及合并返回结果，无需讨论使得代码更加简洁而已。

• 一旦发现p,q结点就返回给上一结点，交付p或q结点在此处的信息，交由上一结点判断
• 如果此节点不是所求结点，递归交由左右子树查找
  • 如果只有左或右子树找到了p或q，此时有两种情况
    • 所求的两个结点位于同一树上，比如均位于左树最左侧，那就会一路向上递归，返回最先找到的节点值（p或q）即为最近祖先
    • 树上只有一个结点，此时依旧向上返回此节点，这样一直层层返回，一定会碰到一个root的左子树也有目标结点，右子树有目标节点，此时该root就会返回自己，即层层返回一定会碰到下面这种情况
  • 如果左右子树都找到了p或q, 则直接返回他们的共同的上一节点root即可，递归由下往上返回结果，所以会返回最近祖先

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == nullptr || root == p || root == q) {return root;}TreeNode* left = lowestCommonAncestor(root->left, p, q);TreeNode* right = lowestCommonAncestor(root->right, p, q);if (left && right) { // 左右都找到return root; // 当前节点是最近公共祖先}return left ? left : right;}
};

力扣链接：删除二叉搜索树的结点

题目：给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

思路：

注意：递归函数返回的是删除完key后的树的根节点，经过调整的符合要求的树，

• 因此key≠当前结点值，只需要将：左或右子树进行删除调整后，连接到当前根节点的对应位置，此时新的树（根节点+左/右孩子），就满足了要求，继续向上返回此根节点
• 当key=当前节点值
  • 当前的root只有左/右孩子，只需要将根节点跳过，该子树就完成删除任务，符合要求了，即直接右/左孩子返回即可
  • 当左右都有时，就需要对树进行调整了，调整的方法即为，找到左子树的最大结点，将右子树直接作为右孩子即可，（二叉搜索树的大小左中右，”左“的最右<中<右），满足条件后，将跳过根节点，直接返回左子树即可。

class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {//遍历到空结点，则删除目标值，依旧返回为空//小问题的解if (!root)return root;if (key < root->val) {root->left = deleteNode(root->left, key);return root;}if (key > root->val) {root->right = deleteNode(root->right, key);return root;}// key==valif (!root->left) {return root->right;}if (!root->right) {return root->left;}// root的左右孩子都在TreeNode* leftMax = root->left;while (leftMax->right)leftMax = leftMax->right;leftMax->right = root->right;return root->left;}
};