算法力扣刷题记载 五十七【236. 二叉树的迩来公共先人】和【235. 二叉搜刮树的迩来公共先人】

媒介

公共先人办理。二叉树和二叉搜刮树条件下的迩来公共先人。
二叉树篇继续。

---

一、【236. 二叉树的迩来公共先人】标题阅读

给定一个二叉树, 找到该树中两个指定节点的迩来公共先人。
百度百科中迩来公共先人的界说为：“对于有根树 T 的两个节点 p、q，迩来公共先人表现为一个节点 x，满意 x 是 p、q 的先人且 x 的深度尽大概大（一个节点也可以是它自己的先人）。”
示例 1：

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

复制代码

示例 2：

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

复制代码

示例 3：

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

复制代码

提示：

1. 树中节点数目在范围 [2, 10^5] 内。
2. -10^9 <= Node.val <= 10^9
3. 所有 Node.val 互不相同 。
4. p != q
5. 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.
  

代码实现【二叉树的迩来公共先人+递归法】

1. class Solution {
2. public:
3.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
4.         if(!root) return nullptr;
5.         if(root->val == q->val || root->val == p->val) return root;
7.         //左
8.         TreeNode* left = lowestCommonAncestor(root->left,p,q);
9.         //右
10.         TreeNode* right = lowestCommonAncestor(root->right,p,q);
11.         //中节点
12.         if(!left && !right) return nullptr;//说明该子树没有p也没有q
13.         else if(!left && right) return right;//一定要返回right。而不是root
14.         else if(!right && left) return left;//一定要返回left。而不是root。
15.         else return root;
16.     }
17. };

复制代码

增补分析【细节】

增补思绪中没提及的环境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放到上面更好一点。
  

1. class Solution {
2. public:
3.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
4.         if(!root) return nullptr;
5.         //没想到在这里直接终止。
6.         //if(root->val == q->val || root->val == p->val) return root;
8.         //左
9.         TreeNode* left = lowestCommonAncestor(root->left,p,q);
10.         //右
11.         TreeNode* right = lowestCommonAncestor(root->right,p,q);
12.         //中节点
13.         if(root->val == p->val || root->val == q->val){
14.             return root;
15.         }else{
16.             if(!left && !right) return nullptr;//说明该子树没有p也没有q
17.             else if(!left && right) return right;//一定要返回right。而不是root
18.             else if(!right && left) return left;//一定要返回left。而不是root。
19.             else return root;
20.         }
21.     }
22. };

复制代码

明白提示给节点值不重复、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:

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

复制代码

示例 2:

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

复制代码

分析:

1. 所有节点的值都是唯一的。
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代码实现【递归】

1. /**
2. * Definition for a binary tree node.
3. * struct TreeNode {
4. *     int val;
5. *     TreeNode *left;
6. *     TreeNode *right;
7. *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8. * };
9. */
11. class Solution {
12. public:
13.     void swap(TreeNode*& p, TreeNode*& q){
14.         if(p->val > q->val){//设定q的值大于p的值。
15.             TreeNode* temp = p;
16.             p = q;
17.             q = temp;
18.         }
19.         return;
20.     }
21.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
22.         //先保证p的值小于q的值
23.         swap(p,q);
24.         //终止条件1：空节点返回空
25.         if(!root) return nullptr;
26.         //终止条件2：中间节点的值在p和q中间,或自身祖先。
27.         if( (p->val < root->val && root->val < q->val) || root->val == p->val || root->val == q->val)
28.             return root;
30.         if(root->val > q->val){
31.             TreeNode* left = lowestCommonAncestor(root->left,p,q);//进到左子树
32.             return left;//此处会直接返回。没有遍历整个树。
33.         }else if(root->val < p->val){
34.             TreeNode* right = lowestCommonAncestor(root->right,p,q);//进到右子树
35.             return right;
36.         }
37.         return nullptr;//走不到这。
38.     }
39. };

复制代码

4.2 【235. 二叉搜刮树的迩来公共先人】参考学习

参考学习链接
学习内容

• 思绪大要划一，但是代码尚有改进点：
  

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

• 以是：代码改进【递归法】
  

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

复制代码

• 迭代法：思绪肯定一样。实行实现下：
  

1. class Solution {
2. public:
3.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
4.         queue<TreeNode*> que;
5.         if(!root) return nullptr;
6.         que.push(root);
7.         while(!que.empty()){
8.             TreeNode* cur = que.front();que.pop();
9.             if(cur->val > p->val && cur->val > q->val && cur->left){
10.                 que.push(cur->left);
11.             }else if(cur->val < p->val && cur->val < q->val && cur->right){
12.                 que.push(cur->right);
13.             }else return cur;
14.         }
15.         return nullptr;//能找到在上一行会直接return，不会走到这一行。
16.     }
17. };

复制代码

对比参考代码：上面照旧有点复杂——用了队列，不外这是迭代模版，肯定能实现。
参考给出：直接用root指针交代下一棒。

---

总结

（接待指正，转载标明出处）