题目
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
_______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4
For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
思路1
找两个节点的公共最小祖先，可以利用递归的思想，即假设我们有个函数，能判断root为根节点的子树里有几个符合的节点（0，1或2个），在递归跳出的过程中，一旦我们发现有返回2个节点的，那这个根元素就肯定是p和q的最低公共节点了。
思路2
假设要找的节点是5和1，那么从根节点通往5的路径是3->5，通往1的路径是3->1。可以用递归方法构造一个路径栈，比较容易地找到路径，然后就变成两条路径的最长公共节点的问题了，“分岔”的地方就是LCA.
相比思路1，这个方法实施起来简单一些，但是要遍历两遍树，会稍微慢一点。
代码1
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int LCASub(TreeNode* root, TreeNode* p, TreeNode* q, TreeNode*& retNode){
//If we find p or q, return 1
//If we find root contains p and q, return 2 and set the retNode to common node
//Else return 0
if(root == NULL)
return 0;
int leftRet = LCASub(root->left, p, q, retNode);
if(leftRet == 2)
return 2;
int rightRet = LCASub(root->right, p, q, retNode);
if(rightRet == 2){
return 2;
}
if(leftRet + rightRet == 2){
retNode = root;
return 2;
} else if(root == p || root == q){
if(leftRet==1 || rightRet == 1){
retNode = root;
return 2;
} else {
return 1;
}
} else {
return leftRet + rightRet;
}
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* retVal = NULL;
LCASub(root, p, q, retVal);
return retVal;
}
};
代码2
class Solution {
public:
bool getPath(TreeNode* root, TreeNode* p, stack<TreeNode*>& path){
//Get path from root to p
//If not available, return false
if(root == NULL || root == p){
path.push(root);
return true;
}
bool foundPath = false;
if(root->left != NULL){
//try left
foundPath = getPath(root->left, p, path);
if(foundPath){
//Mission complete, push current node and return
path.push(root);
return true;
}
}
if(root->right != NULL){
foundPath = getPath(root->right, p, path);
if(foundPath){
path.push(root);
return true;
}
}
return false;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
stack<TreeNode*> pPath;
stack<TreeNode*> qPath;
getPath(root, p, pPath);
getPath(root, q, qPath);
TreeNode* result = NULL;
while(!pPath.empty() && !qPath.empty()){
if(pPath.top() != qPath.top())
break;
result = pPath.top();
pPath.pop();
qPath.pop();
}
return result;
}
};