68.二叉树的最近公共祖先2

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) return right;
    // 如果右子树为空，那么左子树一定是最近公共祖先
    if (right == null) return left;
    // 如果左子树和右子树都不为空，那么root为最近公共祖先
    return root;
}