今�Hの国の呵呵君: [Algorithm]Get Distance Between Two Nodes in Binary Tree
两个Node的距离取决于从node1到node2经过的edge数，如果考虑用类似LCA的解法的话，如果两个node的LCA是其中一个node，因为我们的算法不会再往下递归了，所以没法得到两者的距离。所以这里我们先计算LCA，之后算出node1和node2和LCA的depth，depth1 + depth2 - 2 * depthLCA就是最终的结果。找LCA的时间复杂度是O(n)，因为是binary tree，找depth的时间复杂度也是O(n)，所以总的时间复杂度是O(n)，代码如下：Read full article from 今�Hの国の呵呵君: [Algorithm]Get Distance Between Two Nodes in Binary Tree
No comments:
Post a Comment