剑指offer-49.树中两个节点的最低公共祖先

二叉查找树：

Leetcode : 235. Lowest Common Ancestor of a Binary Search Tree

二叉查找树中，两个节点 p, q 的公共祖先 root 满足 root.val >= p.val && root.val <= q.val。

根据二叉排序树的特点：
如果 root 为 null, 直接返回。
如果 所求两个结点的值都小于 root 的值，则在root的左结点查找。
如果 所求两个结点的值都大于root的值，则在root的右节点查找。
若干一个大于，一个小于，则root就是他们的最低公共祖先。

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

普通二叉树

Leetcode : 236. Lowest Common Ancestor of a Binary Tree

给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。最近公共祖先是两个节点的公共的祖先节点且具有最大深度。

对于下面这棵二叉树

  4
 / \
3   7
   / \
  5   6

LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7

思路：
分治递归的思想：
考虑当前状态
(1) 如果 root == null 就是没找到 => return null
(2) 如果 root == p, 找到，返回这个p；如果 root == q, 找到，返回这个q

(1) & (2) 加一起写成：
if (root == null || root == p|| root == q) {
return root;
}
(3) 分别算出left part and right part 搜索 有没有 ancestor
(4) 如果left part and right part 返回的值不是NULL，说明两个值分别在左子树和右子树, 这样的情况 => 公共祖先只能是root，直接返回root
(5) 如果一个有null，一个不为null，那么他们的公共祖先只可能是不为null的子孩子结点，返回不是 null 的 node

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