Lowest Common Ancestor
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// 找到叶子都没有,返回null
if (!root) return nullptr;
// 如果找到了就返回这个节点
if (root == p || root == q) return root;
// 后续遍历
auto left = lowestCommonAncestor(root->left, p, q);
auto right = lowestCommonAncestor(root->right, p, q);
// 后续遍历可以节点可以获取子节点的信息
// 如果p q都存在与两个子树中
if (left && right)
return root;
// 往上返回 表明来自哪一个子树
if (left) return left;
if (right) return right;
// 如果p q都不在子树中,返回null
return nullptr;
}
};