[LintCode] 578 Lowest Common Ancestor III 解题报告

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.
Return null if LCA does not exist.

Notice
node A or node B may not exist in tree.

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

算法班，未经验证

第32，33行是标志量，通过这两个量来判断是否A，B都已找到匹配。而且匹配到当前root层

Result中node的意义是，按照目前的匹配状况的lca，分为3种：

1. 2个都匹配，node即为lca

2. 1个匹配，匹配到的node

3. 0个匹配，node为null

第35－37行，至少一个匹配，若2个都已经匹配到了，当前root就是lca，否则只有一个匹配到了，就是当前root

第39-41行，在root层有2个匹配，这里有一个隐含的条件，虽然子树返回的node, foundA, foundB不一定有关，但是Result(node, false, false)是不会出现的，Result(null, true, true)， Result(null, true, false), Result(null, false, true)也是不会出现的。

在39-41行，若有2个匹配，且来自不同分支，那么root就是lca

第42－44行，left有至少一个匹配（且right没有匹配）

第45-47行，right有至少一个匹配（且left没有匹配）

最后是没有任何匹配的情况，也可以改为Result(null, false, false)

第23行判断，ret.node是来自与仅仅匹配到的一个node还是真正的lca

 1 public class Solution {
 2     /**
 3      * @param root The root of the binary tree.
 4      * @param A and B two nodes
 5      * @return: Return the LCA of the two nodes.
 6      */
 7     
 8     class Result {
 9         boolean foundA;
10         boolean foundB;
11         TreeNode node;
12         Result(TreeNode node, boolean foundA, boolean foundB) {
13             this.foundA = foundA;
14             this.foundB = foundB;
15             this.node = node;
16         }
17     }
18 
19     public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
20         // write your code here
21         Result ret = helper(root, A, B);
22         if (ret.foundA && ret.foundB) return ret.node;
23         return null;
24     }
25 
26     public Result helper(TreeNode root, TreeNode A, TreeNode B) {
27         if (root == null) return new Result(null, false, false);
28 
29         Result left = helper(root.left, A, B);
30         Result right = helper(root.right, A, B);
31 
32         boolean foundA = left.foundA || right.foundA || root == A;
33         boolean foundB = left.foundB || right.foundB || root == B;
34 
35         if (A == root || B == root) {
36             return new Result(root, foundA, foundB);
37         }
38 
39         if (left.node != null && right.node != null) {
40             return new Result(root, foundA, foundB);
41         }
42         if (left.node != null) {
43             return new Result(left.node, foundA, foundB);
44         }
45         if (right.node != null) {
46             return new Result(right.node, foundA, foundB);
47         }
48         return new Result(null, foundA, foundB);
49     }
50 }