算法力扣刷题记载 五十七【236. 二叉树的迩来公共先人】和【235. 二叉搜刮树的迩来公共先人】
媒介公共先人办理。二叉树和二叉搜刮树条件下的迩来公共先人。
二叉树篇继续。
一、【236. 二叉树的迩来公共先人】标题阅读
给定一个二叉树, 找到该树中两个指定节点的迩来公共先人。
百度百科中迩来公共先人的界说为：“对于有根树 T 的两个节点 p、q，迩来公共先人表现为一个节点 x，满意 x 是 p、q 的先人且 x 的深度尽大概大（一个节点也可以是它自己的先人）。”
示例 1：
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvMjEyOWY5Y2I1ODc3NGNhZWIzOTdmYTVjYTM4NDQyMTgucG5n
输入：root = , p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvZTUwNGY4NWYxOTAwNGI5OTlmMDI2Y2ZiNzkyNTA2NGYucG5n
输入：root = , p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = , p = 1, q = 2
输出：1
提示：
树中节点数目在范围 内。
-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，即子树返回的节点。注意：这里不能返回中心节点。会把迩来公共先人丢掉。
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvNTU0MDdjNTFiNzcyNGM2YTg3NGEwNTYzNWQ5MzRhMjQucG5n
[*] 假如双方子树都为空，分析该中心节点的左右子树不包罗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也没有q
else if(!left && right) return right;//一定要返回right。而不是root
else 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了。）
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvODkxYWM0OThkMThhNDQ1MWIzZjBkMWY1NDY3Mzk4YTUucG5n
接济：没想到停止条件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也没有q
else if(!left && right) return right;//一定要返回right。而不是root
else 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 =
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvMzU4YmU4ZmMxMzE2NDY4OTliNTE0YWZmOTJkNmY1NmYucG5n
示例 1:
输入: root = , p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = , 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，当前节点的值在中心，分析当前节点就是公共先人。
[*]可以画图辅助明白。如下：
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvY2NjNjFjMjYyODIxNDkyYTliMmJiZTZjM2Y4MGMzNDQucG5n
[*]递归函数停止条件：上面已经说了两点停止条件。天然再加上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，不会走到这一行。
}
};
对比参考代码：上面照旧有点复杂——用了队列，不外这是迭代模版，肯定能实现。
参考给出：直接用root指针交代下一棒。
总结
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvNmYzN2FlMDk0MmQzNGZiNWIwYzYyN2M0NzYxODQ1YmQucG5n
（接待指正，转载标明出处）
页:
[1]