LeetCode 236 Lowest Common Ancestor of a Binary Tree
概述
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
注意子节点没有父指针哦。
递归法
根节点肯定是其共同祖先，一直向下直到子节点都不是共同祖先。
好了，现在我们要如何判断子节点是否是共同祖先？只能递归了。
要注意节点本身也是其父节点。
递归套递归，时间复杂度爆炸。
class Solution {
public:
TreeNode* ans;
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
helper(root, p, q);
return ans;
}
void helper(TreeNode* root, TreeNode* p, TreeNode* q) {
ans = root;
if (isCommonAncestor(root->left, p, q)) {
helper(root->left, p, q);
}
if (isCommonAncestor(root->right, p, q)) {
helper(root->right, p, q);
}
}
bool isCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
return isAncestor(root, p) && isAncestor(root, q);
}
bool isAncestor(TreeNode* root, TreeNode* p) {
if (!root) return false;
if (root == p) return true;
if (root->left == p || root->right == p) return true;
return isAncestor(root->left, p) || isAncestor(root->right, p);
}
};
一个可以优化的地方是，对判断节点是否是 p 和 q 的祖先节点可以做一下缓存。
更加直接的递归法
https://mp.weixin.qq.com/s/9RKzBcr3I592spAsuMH45g
从下往上看，从 p 出发，将其父节点做标记，q 同理，则自下向上第一个有双重标记的节点即最近共同祖先。
那要怎么自下向上嘞？后续遍历！
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return nullptr;
if (root == p || root == q) return root;
auto l = lowestCommonAncestor(root->left, p, q);
auto r = lowestCommonAncestor(root->right, p, q);
if (l != nullptr && r != nullptr) { // both are marked, which means root is a common ancestor
return root;
}
if (l == nullptr && r == nullptr) { // which means root is not ancestor of both nodes
return nullptr;
}
return l ? l : r; // root is only a ancestor of one of them, we should mark root
}
};
这个递归函数的返回值有两种，因此不好理解。
其实可以这样理解，前期用作布尔值，后期兼顾用来传递结果。
这也是为啥我们不能随便 return 一个非 null 值来进行标记。