正文
【IT笔试面试题整理】寻找二叉树两节点的最近的公共祖先
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
【试题描述】
求二叉树中任意两个节点的最近公共祖先也称为LCA问题（Lowest Common Ancestor）。
二叉查找树
如果该二叉树是二叉查找树，那么求解LCA十分简单。
基本思想为：从树根开始，该节点的值为t，如果t大于t1和t2，说明t1和t2都位于t的左侧，所以它们的共同祖先必定在t的左子树中，从t.left开始搜索；如果t小于t1和t2，说明t1和t2都位于t的右侧，那么从t.right开始搜索；如果t1<t< t2，说明t1和t2位于t的两侧，那么该节点t为公共祖先。
如果t1是t2的祖先，那么应该返回t1的父节点；同理，如果t2是t1的祖先，应该返回t2的父节点。
【参考代码】
1 public int query(Node t1, Node t2, Node t) {
2 int left = t1.value;
3 int right = t2.value;
4 Node parent = null;
5
6 if (left > right) {
7 int temp = left;
8 left = right;
9 right = temp;
10 }
11
12 while (true) {
13 if (t.value < left) {
14 parent = t;
15 t = t.right;
16 } else if (t.value > right) {
17 parent = t;
18 t = t.left;
19 } else if (t.value == left || t.value == right) {
20 return parent.value;
21 } else {
22 return t.value;
23 }
24 }
25 }
普通二叉树
算法思想：如果一个节点的左子树包含p，q中的一个节点，右子树包含另一个，则这个节点就是p，q的最近公共祖先。
【参考代码】
解法一：
1 public static Node findNCA(Node root, Node p, Node q)
2 {
3 if (isintree(root.left, p) && isintree(root.left, q))
4 return findNCA(root.left, p, q);
5 if (isintree(root.right, p) && isintree(root.right, q))
6 return findNCA(root.right, p, q);
7 return root;
8 }
9
10 public static boolean isintree(Node root, Node node)
11 {
12 if (root == null)
13 return false;
14 if (root == node)
15 return true;
16 return isintree(root.left, node) || isintree(root.right, node);
17 }
解法二：
1 static int TWO_NODES_FOUND = 2;
2 static int ONE_NODES_FOUND = 1;
3 static int NO_NODES_FOUND = 0;
4
5 public static int covers(Node root, Node p, Node q)
6 {
7 int ret = NO_NODES_FOUND;
8 if (root == null)
9 return ret;
10 if (root == p || root == q)
11 ret += 1;
12 ret += covers(root.left, p, q);
13 if (ret == TWO_NODES_FOUND)
14 return ret;
15 return ret + covers(root.right, p, q);
16 }
17
18 private static Node findNCA(Node root, Node p, Node q)
19 {
20 if (q == p && (root.left == q || root.right == q))
21 return root;
22 int nodesFromLeft = covers(root.left, p, q);
23 if (nodesFromLeft == TWO_NODES_FOUND)
24 {
25 if (root.left == p || root.left == q)
26 return root.left;
27 else
28 return findNCA(root.left, p, q);
29 } else if (nodesFromLeft == ONE_NODES_FOUND)
30 {
31 if (root == p)
32 return p;
33 else if (root == q)
34 return q;
35 }
36
37 int nodesFromRight = covers(root.right, p, q);
38 if (nodesFromRight == TWO_NODES_FOUND)
39 {
40 if (root.right == p || root.right == q)
41 return root.right;
42 else
43 return findNCA(root.right, p, q);
44 } else if (nodesFromRight == ONE_NODES_FOUND)
45 {
46 if (root == p)
47 return p;
48 else if (root == q)
49 return q;
50 }
51
52 if (nodesFromLeft == ONE_NODES_FOUND
53 && nodesFromLeft == ONE_NODES_FOUND)
54 return root;
55 else
56 return null;
57 }
解法三：
网上版本：
1 public static int FindNCA(Node root, Node a, Node b, Node out)
2 {
3 if (root == null)
4 return 0;
5 if (root == a || root == b)
6 return 1;
7
8 int iLeft = FindNCA(root.left, a, b, out);
9 if (iLeft == 2)
10 return 2;
11
12 int iRight = FindNCA(root.right, a, b, out);
13 if (iRight == 2)
14 return 2;
15
16 if (iLeft + iRight == 2)
17 out = root;
18
19 return iLeft + iRight;
20 }
这个网上说输出时 当为2时才输出，但是为2时，不能判断如果其中一个是另一个的父亲节点情况。所以理论上应该改为当返回结果
大于0时，就可以输出结果。但是不太确定正确性，应该程序是正确的。
参考：
http://blog.csdn.net/w397090770/article/details/7615447
