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;
    }
};