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.
初次接触这种题可能会没有什么思路，在没有思路的情况下我们就从简单例子开始分析！首先看看3和5，这两个节点分居根节点4的两侧，如果可以从子节点往父节点递推，那么他们将在根节点4处第一次重合；再来看看5和6，这两个都在根节点4的右侧，沿着父节点往上递推，他们将在节点7处第一次重合；最后来看看6和7，此时由于7是6的父节点，故7即为所求。从这三个基本例子我们可以总结出两种思路——自顶向下(从前往后递推)和自底向上(从后往前递推)。
顺着上述实例的分析，我们首先看看自底向上的思路，自底向上的实现用一句话来总结就是——如果遍历到的当前节点是 A/B 中的任意一个，那么我们就向父节点汇报此节点，否则递归到节点为空时返回空值。具体来说会有如下几种情况：
NULL, 则向父节点返回NULL. // 节点不在这棵树中根据此递归模型容易看出应该使用中序遍历来实现。
/**
* 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 中的一个节点！这种情况应该返回空值，但上述实现均返回非空节点。重复节点就不考虑了，太复杂了...
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
if (root == null || root == A || root == B) {
return root;
}
// Divide
TreeNode left = lowestCommonAncestor(root.left, A, B);
TreeNode right = lowestCommonAncestor(root.right, A, B);
// Conquer
if (left != null && right != null) {
return root;
}
if (left != null) {
return left;
}
if (right != null) {
return right;
}
return null;
}
}
其实这个代码只是把上一个版本的代码最后简洁的判断语句改成复杂的多层判断就可以了。同样是分治法实现。
为了解决上述方法可能导致误判的情况，我们可以对返回结果添加计数器来解决。由于此计数器的值只能由子树向上递推，故不能再使用中序遍历，而应该改用后序遍历。
定义pair<TreeNode *, int> result(node, counter)表示遍历到某节点时的返回结果，返回的node表示LCA 路径中的可能的最小节点，相应的计数器counter则表示目前和A或者B匹配的节点数，若计数器为2，则表示已匹配过两次，该节点即为所求，若只匹配过一次，还需进一步向上递推。表述地可能比较模糊，还是看看代码吧。
/**
* 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的节点，如此便保证了该方法的正确性。对这种实现还有问题的在下面评论吧。
leetcode. Lowest Common Ancestor of a Binary Tree Part I | LeetCode - 清晰易懂的题解和实现。 ↩