朴素解法及优化解法。
朴素解法：
考虑寻找 0,8 的最近公共祖先。可以先找到各自的路径：
path_p = 3 1 0
path_1 = 3 1 8
然后找到第一对不同的数（0,8）往前的数（1），就是答案。
class Solution {
public:
void FindPathImpl(stack<TreeNode *> &history, TreeNode *root,
TreeNode *target, bool &over) {
if (over) {
return;
}
history.push(root);
if (root == nullptr) {
return;
}
if (root == target) {
over = true;
return;
}
FindPathImpl(history, root->left, target, over);
if (over) {
return;
} else {
history.pop();
}
FindPathImpl(history, root->right, target, over);
if (over) {
return;
} else {
history.pop();
}
}
deque<TreeNode *> FindPath(TreeNode *root, TreeNode *target) {
stack<TreeNode *> history;
bool found = false;
FindPathImpl(history, root, target, found);
// reverse
deque<TreeNode *> ret;
while (!history.empty()) {
auto top = history.top();
history.pop();
ret.push_back(top);
}
return ret;
}
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
auto sp = this->FindPath(root, p);
auto sq = this->FindPath(root, q);
auto prev = sp.back();
while (!sp.empty() && !sq.empty()) {
if (sp.back() != sq.back()) {
return prev;
}
prev = sp.back();
sp.pop_back();
sq.pop_back();
}
return prev;
}
};
执行用时：28 ms, 在所有 C++ 提交中击败了 10.31%的用户 内存消耗：17.2 MB, 在所有 C++ 提交中击败了 5.99%的用户
还有什么办法？
分类讨论：若 p, q 有公共祖先，则：
- 要么左右枝各一个
- 要么都在同一枝
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
// case 1: one in left, another in right
auto left = lowestCommonAncestor(root->left, p, q);
auto right = lowestCommonAncestor(root->right, p, q);
if (left && right) {
return root;
}
// case 2: both in the same side
auto side = left ? left : right;
return lowestCommonAncestor(side, p, q);
}`
好，然后加入终止条件即可：
class Solution {
public:
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
if (root == nullptr) {
return nullptr;
}
if (root == p || root == q) {
return root;
}
// case 1: one in left, another in right
auto left = lowestCommonAncestor(root->left, p, q);
auto right = lowestCommonAncestor(root->right, p, q);
if (left && right) {
return root;
}
// case 2: both in the same side
auto side = left ? left : right;
return lowestCommonAncestor(side, p, q);
}
};
还可以写更少，但没必要：
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
if (root == nullptr || root == p || root == q) return root;
// case 1: one in left, another in right
auto left = lowestCommonAncestor(root->left, p, q);
auto right = lowestCommonAncestor(root->right, p, q);
if (left && right) return root;
// case 2: both in the same side
return lowestCommonAncestor(left ? left : right, p, q);
}