Lowest Common Ancestor · 數據結構與算法/leetcode/lintcode題解

# Lowest Common Ancestor ### Source - lintcode: [(88) Lowest Common Ancestor](http://www.lintcode.com/en/problem/lowest-common-ancestor/) ~~~ 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. Example 4 / \ 3 7 / \ 5 6 For 3 and 5, the LCA is 4. For 5 and 6, the LCA is 7. For 6 and 7, the LCA is 7. ~~~ ### 題解1 - 自底向上初次接觸這種題可能會沒有什么思路，在沒有思路的情況下我們就從簡單例子開始分析！首先看看`3`和`5`，這兩個節點分居根節點`4`的兩側，如果可以從子節點往父節點遞推，那么他們將在根節點`4`處第一次重合；再來看看`5`和`6`，這兩個都在根節點`4`的右側，沿著父節點往上遞推，他們將在節點`7`處第一次重合；最后來看看`6`和`7`，此時由于`7`是`6`的父節點，故`7`即為所求。從這三個基本例子我們可以總結出兩種思路——自頂向下(從前往后遞推)和自底向上(從后往前遞推)。順著上述實例的分析，我們首先看看自底向上的思路，自底向上的實現用一句話來總結就是——如果遍歷到的當前節點是 A/B 中的任意一個，那么我們就向父節點匯報此節點，否則遞歸到節點為空時返回空值。具體來說會有如下幾種情況： 1. 當前節點不是兩個節點中的任意一個，此時應判斷左右子樹的返回結果。 - 若左右子樹均返回非空節點，那么當前節點一定是所求的根節點，將當前節點逐層向前匯報。// 兩個節點分居樹的兩側 - 若左右子樹僅有一個子樹返回非空節點，則將此非空節點向父節點匯報。// 節點僅存在于樹的一側 - 若左右子樹均返回`NULL`, 則向父節點返回`NULL`. // 節點不在這棵樹中 1. 當前節點即為兩個節點中的一個，此時向父節點返回當前節點。根據此遞歸模型容易看出應該使用中序遍歷來實現。 ### C++ Recursion From Bottom to Top ~~~ /** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @param root: The root of the binary search tree. * @param A and B: two nodes in a Binary. * @return: Return the least common ancestor(LCA) of the two nodes. */ TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) { // return either A or B or NULL if (NULL == root || root == A || root == B) return root; TreeNode *left = lowestCommonAncestor(root->left, A, B); TreeNode *right = lowestCommonAncestor(root->right, A, B); // A and B are on both sides if ((NULL != left) && (NULL != right)) return root; // either left or right or NULL return (NULL != left) ? left : right; } }; ~~~ ### 源碼分析結合例子和遞歸的整體思想去理解代碼，在`root == A || root == B`后即層層上浮(自底向上)，直至找到最終的最小公共祖先節點。最后一行`return (NULL != left) ? left : right;`將非空的左右子樹節點和空值都包含在內了，十分精煉！[leetcode](#) ****> 細心的你也許會發現，其實題解的分析漏掉了一種情況，即樹中可能只含有 A/B 中的一個節點！這種情況應該返回空值，但上述實現均返回非空節點。重復節點就不考慮了，太復雜了... ### 題解 - 自底向上(計數器) 為了解決上述方法可能導致誤判的情況，我們可以對返回結果添加計數器來解決。**由于此計數器的值只能由子樹向上遞推，故不能再使用中序遍歷，而應該改用后序遍歷。** 定義`pair<TreeNode *, int> result(node, counter)`表示遍歷到某節點時的返回結果，返回的`node`表示LCA 路徑中的可能的最小節點，相應的計數器`counter`則表示目前和`A`或者`B`匹配的節點數，若計數器為2，則表示已匹配過兩次，該節點即為所求，若只匹配過一次，還需進一步向上遞推。表述地可能比較模糊，還是看看代碼吧。 ### C++ Post-order(counter) ~~~ /** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @param root: The root of the binary search tree. * @param A and B: two nodes in a Binary. * @return: Return the least common ancestor(LCA) of the two nodes. */ TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) { if ((NULL == A) || (NULL == B)) return NULL; pair<TreeNode *, int> result = helper(root, A, B); if (A != B) { return (2 == result.second) ? result.first : NULL; } else { return (1 == result.second) ? result.first : NULL; } } private: pair<TreeNode *, int> helper(TreeNode *root, TreeNode *A, TreeNode *B) { TreeNode * node = NULL; if (NULL == root) return make_pair(node, 0); pair<TreeNode *, int> left = helper(root->left, A, B); pair<TreeNode *, int> right = helper(root->right, A, B); // return either A or B int count = max(left.second, right.second); if (A == root || B == root) return make_pair(root, ++count); // A and B are on both sides if (NULL != left.first && NULL != right.first) return make_pair(root, 2); // return either left or right or NULL return (NULL != left.first) ? left : right; } }; ~~~ ### 源碼分析在`A == B`時，計數器返回1的節點即為我們需要的節點，否則只取返回2的節點，如此便保證了該方法的正確性。對這種實現還有問題的在下面評論吧。 ### Reference - leetcode > . [Lowest Common Ancestor of a Binary Tree Part I | LeetCode](http://articles.leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html) > - 清晰易懂的題解和實現。 [ ?](# "Jump back to footnote [leetcode] in the text.") - [Lowest Common Ancestor of a Binary Tree Part II | LeetCode](http://articles.leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-ii.html) - 如果存在指向父節點的指針，我們能否有更好的解決方案？ - [Lowest Common Ancestor of a Binary Search Tree (BST) | LeetCode](http://articles.leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-search-tree.html) - 二叉搜索樹中求最小公共祖先。 - [Lowest Common Ancestor | 九章算法](http://www.jiuzhang.com/solutions/lowest-common-ancestor/) - 第一種和第二種方法可以在知道父節點時使用，但第二種 Divide and Conquer 才是本題需要的思想（第二種解法可以輕易改成不需要 parent 的指針的）。