236. 二叉树的最近公共祖先

【题目】：236. 二叉树的最近公共祖先

终止条件：

• 当root到叶节点终止
• 当root是p或q终止（因为要求的是公共祖先，如果遍历到p，就算q还在p的下边，他们的公共祖先还是p）

这也说明了：如果返回的是nullptr，说明p、q不在这棵树中

返回情况：

1. left == nullptr && right == nullptr：说明root的左右子树都没有p、q，直接返回nullptr
2. left != nullptr && right == nullptr：说明p、q在root的左子树中，那么只需要返回left（因为前面只要遇到p或q就会终止，所以此时left就是p、q中相对上边的节点）
3. right != nullptr && left == nullptr：说明p、q在root的右子树中，那么只要返回right即可（原因同上）
4. right != nullptr && left != nullptr：说明p、q分散在root的左右子树中，此时root就是他们的最近公共祖先节点

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 如果root是p 或 q 或 nullptr，就不需要再往下遍历了
        if(root == nullptr || root == p || root == q) {
            return root;
        }
        // 如果root不是p 或 q，就继续遍历root的左右子树
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        
        if(left == nullptr && right == nullptr) {// 如果p 和 q都没找到，更不可能有公共祖先了
            return nullptr;
        }else if(left == nullptr) {// 如果左子树没有p也没有q，那就返回右子树
            return right;
        }else if(right == nullptr) {// 如果右子树没有p也没有q，那就返回左子树
            return left;
        }else {// 如果p和q分别在左右子树中，那就返回root
            return root;
        }
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(n)