|
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.
二叉树的经典问题，也是笔试面试常考问题。
两种思路：第一种比较好想，就是找到两个节点p,q对应的root->....->p和root->....->q的路径，然后比较两个路径，找到最后一公共节点即可。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root || root == p || root == q) return root;
vector<TreeNode*> s,t;
findPath(root, p, s);
findPath(root, q, t);
int k = min(s.size(), t.size()), i = 1;
for(;i<k;++i){
if(s[i] != t[i]) break;
}
return s[i-1];
}
bool findPath(TreeNode* root, TreeNode* node, vector<TreeNode*>& path){
if (root == NULL)
return false;
path.push_back(root);
if (root == node)
return true;
if (root->left && findPath(root->left, node, path) ||
root->right && findPath(root->right, node, path))
return true;
path.pop_back();
return false;
}
};
第二种思路：递归寻找。如果p，q节点有一个是当前root节点，那就直接返回root节点，如果不是，就在左右子树中寻找p，q。如果在一个子树中找到p，另个子树找到q，那么当前root就是最小的公共祖先。如果都在同一个子树上，那就递归在这个子树中寻找p,q的公共祖先。代码非常简单。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
return !left ? right : !right ? left : root;
}
};
后：不知道p,q中如果有一个点不在树中，这种情况有没有考虑过。好像方法二没对这种情况进行讨论。方法一的话对应bool的函数进行一个判断即可。另外方法一的话可以解决二叉树中两个节点之间最短路径这类问题。
| 
转播
