The lowest common ancestor

关于树的问题实在是太多了，不过一般都可以通过递归的方法解决。
下面是两道关于最小父节点的问题，解法可谓简洁明了，而且又是这个人，也只有这个人能写出这样简洁明了的代码了，简直要膜拜啊！

1. Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
2. Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

[leetcode 235] Lowest Common Ancestor of a Binary Search Tree

求二叉搜索树中两个子节点的最近公共父节点，两个子节点有三种情况，一种情况是都在根节点的左边，一种是都在根节点的右边，一种是一个在左边，一个在右边，最后这种情况直接返回根节点即可，而前面两种情况又可以转为上面的子问题，代码如下：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while ((root.val - p.val) * (root.val - q.val) > 0)
            root = p.val < root.val ? root.left : root.right;
        return root;
    }

[leetcode 236] Lowest Common Ancestor of a Binary Tree

这道题对一般的二叉树而言，分别在根节点的左边和右边找两个节点，如果两个节点要么都在根节点的左边，要么都在根节点的右边，那么left和right都不为空，返回根节点；如果不是这个情况，那么返回不为空的(left或者right)，直到有个节点的left和right都不为空为止。代码如下：

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);
    return left == null ? right : right == null ? left : root;
}