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).”
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == NULL || 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直接返回之，避免了开辟空间记录是否出现过p和q的问题（根据返回值是NULL还是p和q区分）。
low的方法：
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == NULL) return NULL;
TreeNode* res = NULL;
dfs(root, p, q, res);
return res;
}
vector<int> dfs(TreeNode* root, TreeNode* p, TreeNode* q, TreeNode*& res) {
vector<int> ret(2, 0), leftsub(2,0), rightsub(2,0);
if(res) return ret;
if(root -> left == root -> right){
if(root == p) ret[0]++;
if(root == q) ret[1]++;
return ret;
}
if(root -> left){
leftsub = dfs(root -> left, p, q, res);
}
if(root -> right){
rightsub = dfs(root -> right, p, q, res);
}
ret[0] = leftsub[0] || rightsub[0] || (root == p);
ret[1] = leftsub[1] || rightsub[1] || (root == q);
if(res == NULL && ret[0] == 1 && ret[1] == 1) res = root;
return ret;
}
