236. 二叉树的最近公共祖先
236. 二叉树的最近公共祖先 - 力扣（LeetCode）
class Solution {
TreeNode *P = nullptr;
TreeNode *Q = nullptr;
TreeNode *Found = nullptr;
bool traverse(TreeNode* TN) {
bool L = false, R = false, S = false;
if (TN->left)
L = traverse(TN->left);
if (TN ->right)
R = traverse(TN->right);
if (TN == P || TN == Q)
S = true;
if (L && R || L && S || R && S) {
Found = TN;
return false;
}
return L || R || S;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
P = p;
Q = q;
traverse(root);
return Found;
}
};
好像写得有点复杂了。
二刷
class Solution {
TreeNode *Target{};
bool Traverse(TreeNode *Root, TreeNode *P, TreeNode *Q) {
if (!Root)
return false;
bool This = (Root == P) || (Root == Q);
bool Left = Traverse(Root->left, P, Q);
bool Right = Traverse(Root->right, P, Q);
if (This && Left || This && Right || Left && Right) {
Target = Root;
// No need to manually stop propagating, since two diverging paths will
// eventually merge into an only way.
// return false;
return true;
}
return This || Left || Right;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
Traverse(root, p, q);
return Target;
}
};
这个模拟解法确实很直观，而且其实也有剪枝，但是好像有点太复杂了……递归还有一种写法就非常非常优雅：
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// The return value can ONLY be one of p, q, and nullptr.
if (!root || root == p || root == q)
return root;
TreeNode *Left = lowestCommonAncestor(root->left, p, q);
TreeNode *Right = lowestCommonAncestor(root->right, p, q);
if (Left && Right)
return root;
return Left ?: Right;
}
};
这整个解法的精华就在开头的 if 上。它的条件语句保证了「但凡返回的不是 nullptr，就只能是 p 和 q 的其中一个」。所以，下面的条件判断也就顺理成章：如果 Left && Right，那就说明都找到了，把 root 向上传递直到冲出递归为止；如果只找到一个，那么 Left ?: Right 会向上传递已经找到的那一个，然后交由上层来继续判断。
注意，第二种递归解法其实用到了一个隐含性质：二叉树从根节点到任意节点的路径是唯一的。所以，除了那唯二两条路径能够使得我们返回非 nullptr 的值以外，剩下的任何路径都会返回 nullptr，这也就意味着完全不用考虑所谓「什么时候该停止传递」的问题。实际上，你会发现我自己的那种写法在进入分支后返回 true 还是 false 都是无所谓的。
存储前驱节点的写法就比较朴素，其实也是模拟的思路，不过注意一下，因为我们要记录的是前驱，所以递归不动点有些许区别。
class Solution {
// Each val is unique. So we can use that as key here.
std::unordered_map<int, TreeNode *> Ancestors;
std::unordered_map<int, bool> Visited;
void FillAncestors(TreeNode *Root) {
Visited[Root->val];
if (Root->left) {
Ancestors[Root->left->val] = Root;
FillAncestors(Root->left);
}
if (Root->right) {
Ancestors[Root->right->val] = Root;
FillAncestors(Root->right);
}
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
FillAncestors(root);
// XXX Possible p == root.
// while (Ancestors[p->val]) {
while (p) {
Visited[p->val] = true;
// In fact the access here also default constructs.
p = Ancestors[p->val];
}
while (!Visited[q->val])
q = Ancestors[q->val];
return q;
}
};
此外也注意一下我写错的那一行。我的本意是通过 operator[] 自动构造一个 nullptr 给全局根节点，但没想到 p 有可能就是根节点。不过事实证明其实完全没必要做这个操作，因为 p = Ancestors[p->val]; 也有自动副作用的。
这里两个哈希表都用 int 当作键是因为题目说明了 val 值是互不相同的。
三刷
class Solution {
TreeNode *Result_;
bool Traversal(TreeNode *Root, TreeNode *P, TreeNode *Q) {
if (!Root)
return false;
// if (Root == P || Root == Q);
// return true;
bool Left = Traversal(Root->left, P, Q);
bool Right = Traversal(Root->right, P, Q);
// Post-order visit.
bool This = (Root == P || Root == Q);
if (This && Left || This && Right || Left && Right)
Result_ = Root;
return This || Left || Right;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
Traversal(root, p, q);
return Result_;
}
};
我靠这个我三刷的时候竟然没写出来？其实写错了之后在改的时候思路有一部分是对的，比如说实际上这题要用的是后序遍历，因为我们需要获得子树的全部信息之后才能进行正确的判定；
但是，同时也应该注意到This在这里的特殊性——This == true并不是这个问题的不动点，因为会有p或q自身为祖先的情况，所以我们真的还是要针对这个情况进行独立判定。最后写出来的逻辑就像上面这样，可能重点还是要记忆一下。
而且这个写法最有趣的还是在于，不用提前终止遍历，因为有This && ...这一长串的谓词，保证了只在一个时刻该谓词是成立的，所以也不用担心被重复赋值。这应该也是拜后序遍历所赐。