【試題描述】

求二叉樹中任意兩個(gè)節(jié)點(diǎn)的最近公共祖先也稱為LCA問題（Lowest Common Ancestor）。

?

二叉查找樹

如果該二叉樹是二叉查找樹，那么求解LCA十分簡單。

基本思想為：從樹根開始，該節(jié)點(diǎn)的值為t，如果t大于t1和t2，說明t1和t2都位于t的左側(cè)，所以它們的共同祖先必定在t的左子樹中，從t.left開始搜索；如果t小于t1和t2，說明t1和t2都位于t的右側(cè)，那么從t.right開始搜索；如果t1<t< t2，說明t1和t2位于t的兩側(cè)，那么該節(jié)點(diǎn)t為公共祖先。

如果t1是t2的祖先，那么應(yīng)該返回t1的父節(jié)點(diǎn)；同理，如果t2是t1的祖先，應(yīng)該返回t2的父節(jié)點(diǎn)。

【參考代碼】

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 }

?

普通二叉樹

算法思想：如果一個(gè)節(jié)點(diǎn)的左子樹包含p，q中的一個(gè)節(jié)點(diǎn)，右子樹包含另一個(gè)，則這個(gè)節(jié)點(diǎn)就是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 }

解法三：
網(wǎng)上版本：

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 }

這個(gè)網(wǎng)上說輸出時(shí) 當(dāng)為2時(shí)才輸出，但是為2時(shí)，不能判斷如果其中一個(gè)是另一個(gè)的父親節(jié)點(diǎn)情況。所以理論上應(yīng)該改為當(dāng)返回結(jié)果
大于0時(shí)，就可以輸出結(jié)果。但是不太確定正確性，應(yīng)該程序是正確的。

?

參考：

http://blog.csdn.net/w397090770/article/details/7615447

?

總結(jié)

以上是生活随笔為你收集整理的【IT笔试面试题整理】寻找二叉树两节点的最近的公共祖先的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。