二叉树的最近公共祖先

当p和q分别为当前root节点的左右子节点时，root就是p和q的最近公共祖先

    //若左右子树中分别存在p和q则返回root
    //若左右子树中都存在p和q则返回NULL
    //否则返回左右子树中不为空的结果
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { 
        if(root == nullptr || root == p || root == q) return root; //遇到 p或q 中的一个就返回

        TreeNode* left = lowestCommonAncestor(root->left, p, q); //若返回值不为空说明左子树存在p / q
        TreeNode* right = lowestCommonAncestor(root->right, p, q); //若返回值不为空说明右子树存在p / q

        if(!left && !right) return nullptr; //left 和 right都为空 说明以root为根节点的子树没有p和q节点
        if(!left) return right; //若左子树没找到右子树找到了返回右子树的结果
        if(!right) return left; //若右子树没找到左子树找到了返回右子树的结果
        return root; //若左右子树分别找到了p和q，说明root为他们的最近公共祖先，返回root
    }