[LintCode] 474 Lowest Common Ancestor II 解题报告

Description
Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

The node has an extra attribute parent which point to the father of itself. The root's parent is null.

Example
For the following binary tree:

4
/
3 7
/
5 6
LCA(3, 5) = 4

LCA(5, 6) = 7

LCA(6, 7) = 7

5/9/2017

算法班

未经验证

思路，把向上遍历的node加到set里面，直到其中一个是null。此时直接返回root

解法一，如果确定A，B都在tree当中：

 1 class Solution {
 2     public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root,
 3                                                  ParentTreeNode A,
 4                                                  ParentTreeNode B) {
 5         // Write your code here   
 6         if (root == null) return null;
 7         Set<ParentTreeNode> s = new HashSet<ParentTreeNode>();
 8         ParentTreeNode tmpA = A;
 9         ParentTreeNode tmpB = B;
10 
11         while (tmpA != null && tmpB != null) {
12             if (s.contains(tmpA)) return tmpA;
13             if (s.contains(tmpB)) return tmpB;
14 
15             s.add(tmpA);
16             s.add(tmpB);
17 
18             tmpA = tmpA.parent;
19             tmpB = tmpB.parent;
20         }
21         return root;
22     }
23 }

解法二，A，B未必在tree当中

 1 class Solution {
 2     public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root,
 3                                                  ParentTreeNode A,
 4                                                  ParentTreeNode B) {
 5         // Write your code here   
 6         if (root == null) return null;
 7         Set<ParentTreeNode> s = new HashSet<ParentTreeNode>();
 8         ParentTreeNode tmpA = A;
 9         ParentTreeNode prevA = null;
10         ParentTreeNode tmpB = B;
11         ParentTreeNode prevB = null;
12 
13         while (tmpA != null || tmpB != null) {
14             if (tmpA != null) {
15                 if (s.contains(tmpA)) return tmpA;
16                 s.add(tmpA);
17                 prevA = tmpA;
18                 tmpA = tmpA.parent;
19             }
20             if (tmpB != null) {
21                 if (s.contains(tmpB)) return tmpB;
22                 s.add(tmpB);
23                 prevB = tmpB;
24                 tmpB = tmpB.parent;
25             }            
26         }
27         if (prevA == root && prevB == root) return root;
28         return null;
29     }
30 }