树

二叉树的最近公共祖先

// 递归终止条件，当前节点为p或者q或者为null，当前节点一定为最小公共祖先，直接返回
        if (root == p || root == q || root == null) {
            return root;
        }
        // 在左子树中找p或者q
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 在右子树中找p或者q
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 如果左子树中没有p和q，则最小公共祖先一定在右子树
        // 如果右子树中没有p和q，则最小公共祖先一定在左子树
        // 如果左右子树中分别又p和q，则最小公共祖先为当前的root节点
        return left == null ? right : right == null ? left : root;

二叉搜索树的最近公共祖先

 // p节点小于root节点，q节点大于root节点，说明root在二者中间，一定为最小公共祖先
        if (root.val > p.val && root.val < q.val) {
            return root;
        }
        // p和q节点均大于root节点，说明p和q都在右子树
        if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        // p和q节点均小于root节点，说明p和q都在左子树
        if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        // p和q有任一节点等于root节点，则当前节点一定是最小公共祖先
        return root;