如何找到二叉树两个节点的最近公共双亲？

二叉树中两个节点的最近公共双亲(Lowest Common Ancestor)是所有这两个节点的双亲节点中离根节点最远的节点，如果其中一个节点是另一个节点的双亲节点，那么符合这个定义的节点就是这个双亲节点，如何快速简单的找到任意的两个节点的最近公共双亲节点是这里要讨论的话题。

首先将这个问题具体化，如果给定的树是一棵二叉查找树，那么这棵树的某些性质就可以为我们所用了。先看代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val>p.val && root.val>q.val) return lowestCommonAncestor(root.left,p,q);
        else if(root.val<p.val && root.val<q.val) return lowestCommonAncestor(root.right,p,q);
        else return root;
    }
}

注意在这段代码中并没有对引用做必要的判空，推敲之后才发现这个看似危险的动作其实是安全的。因为我们将范围限定在了二叉查找树，所以如果root.val>p.val && root.val>q.val这个条件成立，就意味这root节点是一定有左子树的，所以引用root.left是安全的，同样的道理可以检查下一个判断语句。

接着我们讨论广泛意义上的LCA问题，再看代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public 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);
        // we found nodes in both the sides, so return root.
        if( left != null && right != null )
            return root;
        return ( left != null )? left : right;
    }
}

最后一部分可以合并成更加简练：

return left == null ? right : right == null ? left : root;

这段代码在逻辑上包含中序遍历整个二叉树的作用，记录遍历的结果，以此推倒节点之间的关系，思路也是很巧妙的。

该问题来自于LeetCode OJ
- lowest-common-ancestor-of-a-binary-tree
- lowest-common-ancestor-of-a-binary-search-tree