算法力扣刷题记录五十七【236. 二叉树的最近公共祖先】和【235. 二叉搜索树的最近公共祖先】

前言

公共祖先解决。二叉树和二叉搜索树条件下的最近公共祖先。
二叉树篇继续。

一、【236. 二叉树的最近公共祖先】题目阅读

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

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

示例 1：
在这里插入图片描述

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：
在这里插入图片描述

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

树中节点数目在范围 [2, 10^5] 内。
-10^9 <= Node.val <= 10^9
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

二、【236. 二叉树的最近公共祖先】题目解答

弯路（第一次做题时，可能的想法）

二叉树习惯用递归法解决问题，那么需要确定遍历顺序和重复执行的递归逻辑。
本题是二叉树，需要求最近公共祖先，那么父节点应该是最后遍历。所以尝试遍历顺序：后序——左右中。
如何找到统一执行的规律呢？回到中间节点需要处理什么逻辑？

受前几节二叉搜索树中序遍历整合到数组中，那么此处遍历结果数组得到之后，看p,q哪个在前，选择在前面的p或者q？可是无法区分自己是祖先的情况。（不正确）

正确思路获取

参考思路链接

确定后序遍历，因为需要从节点p,q向上退出父节点，所以中间节点最后处理。（左右中）
返回中间节点什么信息？判断左子树中是否存在p或q，判断右子树中是否存在p或q：

如果左子树有p，右子树有q；左子树有q，右子树有p。此时返回中间节点（最近公共祖先）。
如果一边子树为空，另一边子树有p或q之一。此时返回left或者right，即子树返回的节点。注意：这里不能返回中间节点。会把最近公共祖先丢掉。
如果两边子树都为空，说明该中间节点的左右子树不包含p和q。向上返回空。

所以递归函数返回值：TreeNode* 类型；
递归函数终止条件：如果cur是空，return空。如果cur->val是p或q，return cur。

两个终止条件：第一个空判断可以容易想到。
如果第二个终止条件没有想到：影响吗？可以拯救：在中间逻辑先判断该节点是否为p或q，如果是，那么return cur；如果不是，走第2.点的逻辑。
所以第二个终止条件放到中间节点之前，更简单。

总结：左右中：先看左右子树能向中间节点返回什么信息——空节点说明不包含p和q；非空节点说明有p或有q或有p和q。注意，中间节点应该真正返回什么，有的是cur（自身），有的是left或right.

代码实现【二叉树的最近公共祖先+递归法】

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(!root) return nullptr;if(root->val == q->val || root->val == p->val) return root;//左TreeNode* left = lowestCommonAncestor(root->left,p,q);//右TreeNode* right = lowestCommonAncestor(root->right,p,q);//中节点if(!left && !right) return nullptr;//说明该子树没有p也没有qelse if(!left && right) return right;//一定要返回right。而不是rootelse if(!right && left) return left;//一定要返回left。而不是root。else return root;}
};

补充说明【细节】

补充思路中没提及的情况2：自身是祖先——以上代码在哪一处包含

p和q不是包含关系，情况1：肯定是某个中间节点的两边子树；
p和q是包含关系，无论谁包含谁——情况2：如示例2.在某个节点的同一个子树内。if(root->val == q->val || root->val == p->val) return root;将包含者向上返回。（不用深入找q了。）

拯救：没想到终止条件2时

可以这样想：先看自己是不是目标，如果是，返回自己。如果不是，看左右子树有没有包含。
看left和right之前先确定自己不是目标。else return root。
所以把终止条件2放到上面更好一点。

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(!root) return nullptr;//没想到在这里直接终止。//if(root->val == q->val || root->val == p->val) return root;//左TreeNode* left = lowestCommonAncestor(root->left,p,q);//右TreeNode* right = lowestCommonAncestor(root->right,p,q);//中节点if(root->val == p->val || root->val == q->val){return root;}else{if(!left && !right) return nullptr;//说明该子树没有p也没有qelse if(!left && right) return right;//一定要返回right。而不是rootelse if(!right && left) return left;//一定要返回left。而不是root。else return root;}}
};

理解提示给节点值不重复、p和q不相等、p 和 q 均存在于给定的二叉树中

这个提示有用。值不相等，说明p是唯一的节点，没有p1,p2,p3……，return的一定是节点p；q同理。
p和q不相等，且都在二叉树中，说明：
- 情况一：p和q非包含关系。一左一右，说明left和right一个遇到p，一个遇到q。
- 情况二：p和q包含关系。说明left或right先遇到其中之一。

三、【235. 二叉搜索树的最近公共祖先】题目阅读

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
在这里插入图片描述

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

四、【235. 二叉搜索树的最近公共祖先】题目解答

4.1 尝试解答

4.1.1思路【个人】

如果当作普通二叉树，那么上一道题肯定能解决。那么此处就要利用二叉搜索树的性质。

二叉搜索树最大的特点：左子树 < 中间节点 < 右子树，数值能有序整理。这可以给搜索指明方向，就不用搜索整个树。
节点p和节点q，假设p->val < q->val，始终坚持这个原则，如果不是，就要换数据。
大小关系：

如果cur->val > q->val，说明应该遍历左子树，右子树不用遍历，得到左子树的返回之后，直接return left。
如果cur->val < p->val ，说明应该遍历右子树，左子树不用遍历，得到右子树的返回之后，直接return right。
如果p->val < cur->val < q->val，当前节点的值在中间，说明当前节点就是公共祖先。
可以画图辅助理解。如下：

递归函数终止条件：上面已经说了两点终止条件。自然再加上cur为空的情况。
递归函数返回值：返回节点类型。

4.1.2代码实现【递归】

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/class Solution {
public:void swap(TreeNode*& p, TreeNode*& q){if(p->val > q->val){//设定q的值大于p的值。TreeNode* temp = p;p = q;q = temp;}return;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//先保证p的值小于q的值swap(p,q);//终止条件1：空节点返回空if(!root) return nullptr;//终止条件2：中间节点的值在p和q中间,或自身祖先。if( (p->val < root->val && root->val < q->val) || root->val == p->val || root->val == q->val) return root;if(root->val > q->val){TreeNode* left = lowestCommonAncestor(root->left,p,q);//进到左子树return left;//此处会直接返回。没有遍历整个树。}else if(root->val < p->val){TreeNode* right = lowestCommonAncestor(root->right,p,q);//进到右子树return right;}return nullptr;//走不到这。}
};

4.2 【235. 二叉搜索树的最近公共祖先】参考学习

参考学习链接

学习内容

思路大体一致，但是代码还有改进点：

判断条件的处理上：中间root->val比p和q的值都大，那么遍历左子树；中间root->val比p和q的值都小，那么遍历右子树。剩下就是root->val在中间，直接返回即可。
因此：不需要swap(p,q) 来始终保持q的值比p大；但是第一次做，这是最直观，方便分析的思路。

所以：代码改进【递归法】

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//终止条件：空节点返回空if(!root) return nullptr;if(root->val > q->val && root->val > p->val){TreeNode* left = lowestCommonAncestor(root->left,p,q);//进到左子树//没有加left为空的判断，因为题目说p和q存在。严格来说加上更通用。if(left) return left;//此处会直接返回。没有遍历整个树。}else if(root->val < p->val && root-=>val < q->val){TreeNode* right = lowestCommonAncestor(root->right,p,q);//进到右子树if(right) return right;}//中return root;//剩余情况。}
};

迭代法：思路肯定一样。尝试实现下：

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {queue<TreeNode*> que;if(!root) return nullptr;que.push(root);while(!que.empty()){TreeNode* cur = que.front();que.pop();if(cur->val > p->val && cur->val > q->val && cur->left){que.push(cur->left);}else if(cur->val < p->val && cur->val < q->val && cur->right){que.push(cur->right);}else return cur;}return nullptr;//能找到在上一行会直接return，不会走到这一行。}
};