算法1

(后续遍历，递归) $O(n)$

后序遍历二叉树，如果遍历到的当前节点为cur。因为是后序遍历，所以先处理cur的两棵子树。假设cur左子树时返回left，右子树返回right
1. 如果cur为null或p，q，返回cur
2. 如果left和right都为空，说明cur左右子树都没有p,q，返回null
3. 如果都不为空，说明左子树上发现过p或q，右子树同理，并在cur相遇，则返回cur
4. 如果left和right其中一个是null，另一个不为空，直接返回不为空的那个节点即是公共祖先。

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||root==p||root==q){
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left!=null&&right!=null){
            return root;
        }

        return left!=null?left:right;
    }
}