给定一个二叉树，找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例：

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

				

					
				
				

					
				
				

					
				
				

					
				
			

题解：root：当前树的根节点；p：要寻找的第一个节点；q：要寻找的第二个节点。返回值类型是 TreeNode，表示找到的最近公共祖先节点。

如果当前节点是否为 p 或 q，或者是否为空节点。则返回 root 节点，因为我们找到了其中一个节点。否则返回 null，表示没有找到任何节点。
递归调用分别搜索左子树和右子树，结果存储在 left 和 right 中。
如果 left 和 right 都不为 null，这意味 p 和 q 分别在 root 的左右子树中，因此当前节点是它们的最近公共祖先。
如果 left 为 null，说明 p 和 q 都不在左子树中，那么返回 right，即右子树中的结果。
如果 right 为 null，说明 p 和 q 都不在右子树中，那么返回 left，即左子树中的结果。

时间复杂度为 O (N)，其中 N 是节点数，空间复杂度为 O (H)，H 是树的高度。