题目：
输入两个树结点，求它们的最低公共祖先。
分析：
分以下几种情况考虑：
- 这棵树是二叉树，并且是二叉搜索树。
- 不是二叉搜索树，甚至不是二叉树，只是普通的树，有指向父结点的指针。
- 不是二叉搜索树，甚至不是二叉树，只是普通的树，没有指向父结点的指针。
解法：
第一种情况：
二叉搜索树是有序的，对于某个结点来说，它的左子树结点<当前结点<右子树结点。所以从树的根节点开始和两个结点进行比较，如果根节点比两个结点都大，那么最低公共祖先位于根节点的左子树中，如果根节点比两个结点都小，那么最低公共祖先位于根节点的右子树中，按照这个规则进行递归遍历，直到某个结点的值介于两个结点值之间，那么这个结点就是最低公共祖先了。
第二种情况：
对于每个结点，既然有指向父结点的指针，那么可以从两个结点开始，都向上遍历直到根节点，那么就会得到两个链表，现在的问题转换成求两个链表的第一个公共节点问题，可以参考这篇文章。
第三种情况：
从根节点开始遍历一棵树，每遍历到一个结点时，判断两个输入的结点在不在它的子树中，如果在它的子树中，则分别遍历它的所有子结点，判断两个输入结点在不在子树中，直到找到一个这样的结点为止：它的子树中同时包含输入的两个输入的结点，但是它的子结点中不同时包含两个输入的结点。
在这个判断过程中，会有很多重复的步骤，还是可以优化的。
从根节点开始遍历，先找到一条从根节点到输入结点的路径，并把这条路径以链表的形式保存起来，再用同样的方法找到跟结点到另一个输入结点的路径，并把这条路径以链表的形式保存起来。然后遍历两个链表，直到碰到这样一个结点：两个链表的第i位结点相同，第i+1位结点不相同了。那么第i位结点就是最低公共祖先了。 | 
转播
