红鸟pay bill 的新手问题# Money - 海外理财
h*o
1 楼
请教正确答案。
网上答案是下面这样的，但如果有个child不存在哪？难道返回另一个child?
网上还有种方法用inorder找candidate, 再用preorder找最先出现的candidate，那如
果一个child不存在， 不就找到root了吗？
Node* find_lowest_common_ancestor_BT(Node* root, Node* child1, Node* child2){
if (!root) return NULL;
Node* left=NULL;
Node* right= NULL;
//if either child1 or 2 are root than root is LCA
//and since this algorithm goes from top to down, in the case of one
child is
//ancestor of the other child, the ancestor child will be hit and return.
int value = root->value();
if (value == child1->value() || value == child2->value()) return root;
left = find_lowest_common_ancestor_BT(root->left(), child1, child2);
right = find_lowest_common_ancestor_BT(root->right(), child1, child2);
if (left && right) return root;
else if (left) return left;
else return right; //include the case if left==right==NULL, return NULL;
}
网上答案是下面这样的，但如果有个child不存在哪？难道返回另一个child?
网上还有种方法用inorder找candidate, 再用preorder找最先出现的candidate，那如
果一个child不存在， 不就找到root了吗？
Node* find_lowest_common_ancestor_BT(Node* root, Node* child1, Node* child2){
if (!root) return NULL;
Node* left=NULL;
Node* right= NULL;
//if either child1 or 2 are root than root is LCA
//and since this algorithm goes from top to down, in the case of one
child is
//ancestor of the other child, the ancestor child will be hit and return.
int value = root->value();
if (value == child1->value() || value == child2->value()) return root;
left = find_lowest_common_ancestor_BT(root->left(), child1, child2);
right = find_lowest_common_ancestor_BT(root->right(), child1, child2);
if (left && right) return root;
else if (left) return left;
else return right; //include the case if left==right==NULL, return NULL;
}
