Given a binary tree, find the lowest common ancestor of two given nodes in the tree. Each node contains a parent pointer which links to its parent.
Note:
This is Part II of Lowest Common Ancestor of a Binary Tree. If you need to find the lowest common ancestor without parent pointers, please read Lowest Common Ancestor of a Binary Tree Part I.
_______3______ / \ ___5__ ___1__ / \ / \ 6 _2 0 8 / \ 7 4
If you are not so sure about the definition of lowest common ancestor (LCA), please refer to my previous post:Lowest Common Ancestor of a Binary Search Tree (BST) or the definition of LCA here. Using the tree above as an example, the LCA of nodes 5 and 1 is 3. Please note that LCA for nodes 5 and 4 is 5.
In my last post: Lowest Common Ancestor of a Binary Tree Part I, we have devised a recursive solution which finds the LCA in O(n) time. If each node has a pointer that link to its parent, could we devise a better solution?
Hint:
No recursion is needed. There is an easy solution which uses extra space. Could you eliminate the need of extra space?
An easy solution:
As we trace the two paths from both nodes up to the root, eventually it will merge into one single path. The LCA is the exact first intersection node where both paths merged into a single path. An easy solution is to use a hash table which records visited nodes as we trace both paths up to the root. Once we reached the first node which is already marked as visited, we immediately return that node as the LCA.
Node *LCA(Node *root, Node *p, Node *q) { hash_set<Node *> visited; while (p || q) { if (p) { if (!visited.insert(p).second) return p; // insert p failed (p exists in the table) p = p->parent; } if (q) { if (!visited.insert(q).second) return q; // insert q failed (q exists in the table) q = q->parent; } } return NULL; }
The run time complexity of this approach is O(h), where h is the tree’s height. The space complexity is also O(h), since it can mark at most 2h nodes.
The best solution:
A little creativity is needed here. Since we have the parent pointer, we could easily get the distance (height) of both nodes from the root. Once we knew both heights, we could subtract from one another and get the height’s difference (dh). If you observe carefully from the previous solution, the node which is closer to the root is alwaysdh steps ahead of the deeper node. We could eliminate the need of marking visited nodes altogether. Why?
The reason is simple, if we advance the deeper node dh steps above, both nodes would be at the same depth. Then, we advance both nodes one level at a time. They would then eventually intersect at one node, which is the LCA of both nodes. If not, one of the node would eventually reach NULL (root’s parent), which we conclude that both nodes are not in the same tree. However, that part of code shouldn’t be reached, since the problem statement assumed that both nodes are in the same tree.
int getHeight(Node *p) { int height = 0; while (p) { height++; p = p->parent; } return height; } // As root->parent is NULL, we don't need to pass root in. Node *LCA(Node *p, Node *q) { int h1 = getHeight(p); int h2 = getHeight(q); // swap both nodes in case p is deeper than q. if (h1 > h2) { swap(h1, h2); swap(p, q); } // invariant: h1 <= h2. int dh = h2 - h1; for (int h = 0; h < dh; h++) q = q->parent; while (p && q) { if (p == q) return p; p = p->parent; q = q->parent; } return NULL; // p and q are not in the same tree }
From:
http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-ii.html
相关推荐
Range Minimum Query and Lowest Common Ancestor[翻译]1
1123.Lowest_Common_Ancestor_of_Deepest_Leaves最深叶节点的最近公共祖先【LeetCo
Lowest Common Ancestor of a Binary Search Tree ...According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has b
Given a rooted binary tree, return the lowest common ancestor of its deepest leaves. Recall that: The node of a binary tree is a leaf if and only if it has no children The depth of the root of ...
lowest common ancestor
非技术人员(包括传教士/儿童/老年人)的简单圣经免费软件小 1.2 兆下载与 OT+NT。 < 1 秒启动和搜索甚至在过时的最低公分母 486 上(1 GB 高清、640*480 分辨率、16 mb 内存、无 CD、28.8 调制解调器、Win95)
针对已有方法不能正确求解基于ELCA(exclusive lowest common ancestor)语义的相关关键字节点(RKN,relevant keyword node)的问题,提出RKN的形式化定义及相应的RKN-Base算法。该算法通过顺序扫描每个关键字节点一次...
LCA(lowest common ancestor) ---, 5.贪婪 6. Manacher/KMP算法 (未完成) 7. 添加 8. 指针 滑动窗口 9.前缀总和 10.递归/DFS 11.棘手的方法 (未完成) 12. 堆栈 Monotonic_Stack 13. 14. 数据结构 每周比赛 第一...
tictax:Web服务的流序列分类 使用One Codex和EBI API从命令行或Python快速便捷地实现最低的祖先(LCA)分配。 以正确的方向吹风,每秒可发出约100个请求。... kmer-lca Lowest common ancestor sequ
This program calculates the lowest common multiple of two numbers using Euclid s algorithm. To do this we will read the two numbers and we do accounts required to calculate
Cyclone® III device family offers a unique combination of high functionality, ...■ Cyclone III—lowest power, high functionality with the lowest cost ■ Cyclone III LS—lowest power FPGAs with security
要在控制台中运行特定问题,请转至文件test,将调用添加到测试函数( test() ),然后在控制台node <problem> (例如, node LeetcodeProblems/Lowest_Common_Ancestor_of_a_Binary_Tree.js )。 Leetcode问题 名称...
5.1.2 Lowest Common Ancestor (LCA) 53 5.1.3 Reduction from LCA to RMQ 56 5.1.4 From RMQ to LCA 57 5.1.5 An(N), O(1)> algorithm for the restricted RMQ 60 5.1.6 An AC programme 61 5.2 最长公共子序列LCS ...
5.1.2 Lowest Common Ancestor (LCA) 53 5.1.3 Reduction from LCA to RMQ 56 5.1.4 From RMQ to LCA 57 5.1.5 An(N), O(1)> algorithm for the restricted RMQ 60 5.1.6 An AC programme 61 5.2 最长公共子序列LCS ...
此指标依据输入参数显示周期内的最小价格。
Lowest common multiple for Linux v2.13.6.
The Spartan®-7 family is the lowest density with the lowest cost entry point into the 7 series portfolio. The Artix®-7 family is optimized for highest performance-per-watt and bandwidth-per-watt ...
PCB design techniques for lowest-cost EMC
It begins with a global introduction, from the high-level view to the lowest common denominator (the chip itself), then moves on to the three main building blocks of an SOC (processor, memory, and ...
cyclone4-白皮书-lowest-system-cost1