求树中两个节点的最低公共祖先節点

这个题可能有几种不同的条件那这样就是不同的问题

(1) 树是二叉树，且是二叉搜索树

思路：如果是二叉搜索树，二叉搜索树是排序過的位于左子树的节点都比父节点小，位于右子树的节点都比父节点大我们只需要从树的根节点开始和两个输入的节点进行比较。如果当前节点的值比两个节点的值都大最低公共祖先结点一定在当前结点的右子树。如果当前节点的值比两个节点的值都最低公共祖先節点一定在当前结点的左子树。

如果一个结点比当前结点大一个比 当前结点小，则最低公共祖先节点为当前结点 (2) 树的结点有指向父节點的指针

这个问题可以转换为求两个链表的第一个公共节点。

从树的每一个叶子节点开始都有一个由指向父节点的指针串起来的链表这些链表的尾指针都是树的根节点。
输入两个节点那么这两个节点位于两个链表上，他们的最低公共祖先刚好就是这两个链表的第一个公囲节点
比如输入F和H，F在链表F-D-B-A上而H在链表H-E-B-A上,这两个链表的第一个交点B刚好也是它们的最低公共祖先

(3)没有指向父节点的指针

用两个链表分別保存从根节点到输入的两个节点的路径，然后把问题转换成两个链表的最后公共节点

（1）如果两个节点分别在根节点的左子树和右子樹，则返回根节点
（2）如果两个节点都在左子树则递归处理左子树；如果两个节点都在右子树，则递归处理右子树

先求从根节点到两个節点的路径然后再比较对应路径的节点就行，最后一个相同的节点也就是他们在二叉树中的最低公共祖先节点