您的位置:首页 > 财经 > 金融 > 天津网站优化排名_企业网站建设怎么样_软文街怎么样_google关键词搜索技巧

天津网站优化排名_企业网站建设怎么样_软文街怎么样_google关键词搜索技巧

2024/12/23 12:36:14 来源:https://blog.csdn.net/ok1382038/article/details/143977801  浏览:    关键词:天津网站优化排名_企业网站建设怎么样_软文街怎么样_google关键词搜索技巧
天津网站优化排名_企业网站建设怎么样_软文街怎么样_google关键词搜索技巧

什么是最近公共祖先LCA

LCA:在一个树中,距离两个节点p,q最近可以是其本身并且同时包含这两个子节点的节点

题目连接

Leetcode 236 - LCA
Leetcode 1644 - LCA II
Leetcode 1650 - LCAIII
Leetcode 1123 - LCA of Deepest leaves

基本思路

Leetcode 236 - LCA
Leetcode 1644 - LCA II
求解LCA的基本思路就是分治法,两个节点的相对位置关系有三种情况:

  1. p和q在同一侧某个子树中,比如下图 p在H点,q在B点。
  2. p和q在两侧不同子树中,比如下图p在D点,q在C点
  3. 边界情况,p,q中有一个节点不存在在该树中

基于上述三种情况,分治递归过程中如果当前节点是p 或者 q那么返回该节点如果当前节点不是p, q查看左右子树递归返回结果

  1. 如果左右有一个是p或者q或者一个非空节点(说明找到了p, q的LCA)那么返回那个点
  2. 如果左右既有p又有q那么返回当前节点说明当前点就是LCA, 如果左右都是空指针那么返回空指针说明p, q和LCA都没有找到。
    解决第三种情况可以建立一个count, 遇到p和q都count++最后返回LCA时保证count==2再返回即可

二叉树示意图

代码如下
class Solution {
public:int count = 0;TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {auto res = dc(root, p, q);return count==2? res: nullptr;}TreeNode* dc(TreeNode* root, TreeNode* p, TreeNode* q) {if (!root) return nullptr;auto l = dc(root->left, p, q);auto r = dc(root->right, p, q);if (root==p || root==q) {count++;return root; } else if ((l==q && r==p) || (l==p && r==q)) return root;else return !l? r: l;}};

时间复杂度: O ( N ) \mathcal{O}(N) O(N) N代表树节点总数
空间复杂度: O ( H ) \mathcal{O}(H) O(H) H代表树的深度,也就是栈的深度

Leetcode 1650

题目描述也是求解两个节点LCA但是树的结构中提供了parent这个节点,树有保存父节点。这道题思路就和 Leetcode 160 找到两个相交链表的相交点。p和q保证是同一个树的两个节点。

基本思路就是让p和q一直通过parent向上层移动,如果p到了root就把p指向q继续移动,如果q到了root就把q指向p继续移动,p和q最后一定会相交在相交点位置,返回这个点就是LCA

为什么一定会相交在相交点LCA位置?

  • 假设p到LCA的距离是 x, q到LCA的距离为y, LCA到root的距离为z
  • 根据上面的思路,p总共移动距离 x+z+y ; q总共移动距离 y+z+x 移动距离相等并在LCA处相交
代码如下
class Solution {
public:Node* lowestCommonAncestor(Node* p, Node * q) {/*[1,2,3,null,4]12  34    和找两个链表的第一个相交点类似// 第一种左右两边p -> 1 -> 2 ->3 ->4 ->5->6q ->7a + c + b b + c + a// 第二种没到终点前找到另一个就返回另一个p -> 2-> qp = 2, q = 4p = 1, q = 2a + b b + a      */auto pp = p;auto qq = q;while (p && q) {if (q==p) return q;q = q->parent;p = p->parent;// 如果p或者q就是LCA,那么移动p,q时后面的点一定会走到前面的点,直接返回这个点即可if (q==pp || p==qq) return q==pp? pp: qq;//到root了,回到另一个点pp或着qq继续走直到相遇if (!q) q=pp; if (!p) p=qq;}return nullptr;}
};

时间复杂度:通常 O ( X + Y + Z ) \mathcal{O}(X+Y+Z) O(X+Y+Z) x指p到LCA经过节点数,y指q到LCA经过节点数, z指LCA到root经过节点数
空间复杂度: O ( 1 ) \mathcal{O}(1) O(1)

Leetcode 1123

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com