首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    最近公共祖先详解_共同祖先

    最近公共祖先 带查询的节点为x和y节点,书的深度为d 暴力求解:设置访问数组vis[N],以此遍历x的父节点并做标记,然后再遍历y的父节点,第一个被做标记的就是公共祖先,时间复杂度为O(d)...倍增法:f[i][j]代表当前节点向上走 2 j 2^j 2j所能走到的节点,其中 0 ≤ j ≤ ⌈ l o g ( d ) ⌉ 0\leq j \leq \lceil log(d) \rceil 0...≤j≤⌈log(d)⌉,时间复杂度为O(logn),另外还需要设置dist[N]代表节点i到根的距离+1,哨兵:如果从i开始跳 2 j 2^j 2j步会跳过根节点,那么f[i][j] = 0,dist[...root]=0 Tarjan离线算法:将每一个搜索过的点归类到他的代表节点中去,代表节点就是搜索过的节点与当前节点的公共祖先。...时间复杂度O(n) 倍增法 先将两个点跳到同一层 再让两个点往上跳,一直跳到他们的公共祖先的下一个几点。我们跳的时候是基于二进制拼凑的思想,从最高位到最低位判断。

    45330

    节点,枝,根,叶,度,层深度高度,双亲孩子兄弟,祖先后代,森林

    下图中,根节点0有3个子树,度为3;节点1有2个子树,度为2;节点3,5分别只有一个子树,度为1。叶(leaf)也可以用度来定义:度为0的节点称为叶(leaf)。...一个节点到下方的叶的最大层级数之差称为节点的高度(height),如节点1位于层1,下方的叶子2,4位于层2,所以节点1的高度是1;同理,节点3的高度也是1,节点5的高度是2,节点2本身是叶,其高度是0...八、祖先/后代(ancestor/descendant) 在一颗树中选定根(root)后,一个点的双亲、双亲的双亲、……都是此点的祖先(ancestor),根节点是所有子节点祖先,注意双亲(parent...)也属于祖先。...因此,祖先是一个集合概念。同理,一个点的孩子、孩子的孩子、……都是此点的后代(descendant),后代也是一个集合概念。 九、森林(forest) 很多颗树的集合称为森林。

    4.5K10

    算法练习(14)-二叉树中2个节点的最近公共祖先

    比如这颗树,给定2个节点: 4、5 ,它们的最近公共祖先节点为2。类似的,如果是3、5,它们的最近公共祖先节点为1。...left : right; } 这个代码很短, 但不太好理解 , 先分析下一颗树中的2个节点X、Y,它们最近公共祖先的情况: 只会出现这2类情况: 1、节点X在Y的某1侧子树中(反过来也一样,...Y出现在X的某1侧子树中),即:1个节点就是另1个的最近公共祖先。...|| root == n2) //在左右子树遍历过程中,如果发现当前节点就是n1或n2,直接返回,因为下面的子节点,肯定不可能再是它俩的公共祖先节点了 ) {...X与Y汇聚于当前节点,这个节点就是最近的公共祖先

    69610

    最近公共祖先LCA

    最近公共祖先(Lowest Common Ancestors,LCA)指有根树中距离两个节点最近的公共祖先祖先指从当前节点到树根路径上的所有节点。...u和v的公共祖先指一个节点既是u的祖先,又是v的祖先。u和v的最近公共祖先指距离u和v最近的公共祖先。若v是u的祖先,则u和v的最近公共祖先是v。 可以使用LCA求解树上任意两点之间的距离。...F[i, j]表示i的2^j辈祖先,即i节点向根节点走2^j步到达的节点。...F[i, j]表示i的2^j辈祖先,即i节点向根节点走2^j步到达的节点。...总结:按照增量递减的方式,到达的节点相同时,什么也不做;到达的节点不同时,同时上移,直到增量为0。此时x、y的父节点为公共祖先节点

    85110

    LCA 最近公共祖先

    :     在一棵没有环的树上,每个节点肯定有其父亲节点祖先节点,而最近公共祖先,就是两个节点在这棵树上深度最大的公共的祖先节点。     ...换句话说,就是两个点在这棵树上距离最近的公共祖先节点。     所以LCA主要是用来处理当两个点仅有唯一一条确定的最短路径时的路径。     ...有人可能会问:那他本身或者其父亲节点是否可以作为祖先节点呢?     答案是肯定的,很简单,按照人的亲戚观念来说,你的父亲也是你的祖先,而LCA还可以将自己视为祖先节点。     ...6.若是v已经被访问过了,则可以确认u和v的最近公共祖先为v被合并到的父亲节点a。     遍历的话需要用到dfs来遍历(我相信来看的人都懂吧...)...表示2已经被搜完,更新f[2]=1,继续搜3,发现3有一个子节点6; 搜索6,发现6没有子节点,则寻找与6有关系的点,发现4和6有关系; 此时vis[4]=1,所以它们的最近公共祖先为find(4)

    1.5K80

    节点与其祖先之间的最大差值(二叉树DFS)

    题目 给定二叉树的根节点 root,找出存在于不同节点 A 和 B 之间的最大值 V,其中 V = |A.val - B.val|,且 A 是 B 的祖先。...(如果 A 的任何子节点之一为 B,或者 A 的任何子节点是 B 的祖先,那么我们认为 A 是 B 的祖先) ?...示例: 输入:[8,3,10,1,6,null,14,null,null,4,7,13] 输出:7 解释: 我们有大量的节点与其祖先的差值,其中一些如下: |8 - 3| = 5 |3 - 7| =...提示: 树中的节点数在 2 到 5000 之间。 每个节点的值介于 0 到 100000 之间。...解题 深度优先搜索,从根节点到每个叶子节点,记录到当前位置的最大最小值,达到叶子节点时,做差,取abs最大的 class Solution { int maxdiff = 0; public:

    76710
    领券