[leetcode/lintcode 题解] 微软面试题:最近公共祖先 II
資深大佬 : zzzrf 10
给一棵二叉树和二叉树中的两个节点,找到这两个节点的最近公共祖先 LCA 。 两个节点的最近公共祖先,是指两个节点的所有父亲节点中(包括这两个节点),离这两个节点最近的公共的节点。 每个节点除了左右儿子指针以外,还包含一个父亲指针 parent,指向自己的父亲。
在线评测地址
样例 1
输入:{4,3,7,#,#,5,6},3,5 输出:4 解释: 4 / 3 7 / 5 6 LCA(3, 5) = 4
样例 2
输入:{4,3,7,#,#,5,6},5,6 输出:7 解释: 4 / 3 7 / 5 6 LCA(5, 6) = 7
解题思路
- 这道题与 88. 最近公共祖先相似,不同的是该题的节点有父指针,所以我们应该充分利用这个信息。我们可以用 hashset 来解这道题。
算法流程
- 建立集合 parentSet,用于存储 A 的祖先节点。
- 首先,从 A 向上遍历到 root,将路径中的节点都存储到 parentSet 中。
- 然后,从 B 向上遍历,判断经过的每个节点是否同时也在 parentSet 中,第一个出现在 parentSet 中的点即为 A 和 B 的最近公共祖先。
复杂度分析
- 时间复杂度:O(k),k 为树的高度。最差情况下,A 是叶节点,从 A 遍历到 root 需要 O(k)的时间。平均情况下时间复杂度也为 O(k)。
- 空间复杂度:O(k),k 为树的高度。最差情况下,A 是叶节点,集合中需要存储从 A 到 root 的所有节点。平均情况下空间复杂度也为 O(k)。
public class Solution { /* * @param root: The root of the tree * @param A: node in the tree * @param B: node in the tree * @return: The lowest common ancestor of A and B */ public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root, ParentTreeNode A, ParentTreeNode B) { Set parentSet = new HashSet<>(); // 把 A 的祖先节点都加入到哈希表中 ParentTreeNode curr = A; while (curr != null) { parentSet.add(curr); curr = curr.parent; } // 遍历 B 的祖先节点,第一个在哈希表中出现的即为答案 curr = B; while (curr != null) { if (parentSet.contains(curr)) { return curr; } curr = curr.parent; } return null; } }
更多题解参考
大佬有話說 (0)