Q68_树中两个节点的最低公共祖先.java

package com.algorithm.demo.剑指Offer;

/**
 * 求树中两个节点的最低公共左线，不能说只是一道题目，应该说是一组题目，不同调价下的题目是完全不一样的。
 * 是否为二叉搜索树？
 * 二叉搜索树是排序过的，位于左子树的节点都比父节点小，而位于右子树的节点都比父节点大，只需要从树的根节点开始和两个输入的节点进行比较。
 * 如果当前节点的值比两个节点的值都大，那么最低的共同父节点一定在当前节点的左子树中，下一步遍历当前节点的左子节点。
 * 如果当前节点的值比两个节点的值都小，那么最低的共同父节点一定在当前节点的右子树中，下一步遍历当前节点的右子节点。
 * 在树中从上到下找到第一个在两个输入节点的值之间的节点就是最低的公共祖先。
 * 树的节点是否有指向父节点的指针？
 * 如果书中的每个节点(除根节点之外)都有一个指向父节点的指针，那么这个问题可以转换成求两个链表的第一个公共节点。假设书中节点中指向父节点的指针是pParent
 * 那么从树的每个叶节点开始都有一个由指针pParent串起来的链表，这些链表的尾指针都是树的根节点。输入两个节点，那么这两个节点位于两个链表上，他们的
 * 最低公共祖先刚好是这两个链表的第一个公共节点。
 *              A
 *          B        C
 *     D         E
 * F       G  H  I  J
 * 例如输入的两个的两个节点分别为F和H，那么F在链表 F -> D -> B ->A
 * 而H在链表 H -> E -> B -> A 上，这两个链表的第一个节点B刚好也是他们的最低公共祖先。
 *
 * 如果没有指向父节点的指针。
 * 所谓两个节点的公共左线，值得是这两个节点都出现在某个节点的自述中。可以从根节点开始遍历一棵树，没遍历到一个节点时，
 * 判断两个输入节点是不是在它的子树中。如果在子树中，则分别遍历它的所有子节点，并判断两个输入节点是不是在他们的自述中。
 * 这样从上到下一直找到的一个节点，它自己的子树中同时包含两个输入的节点而它的子节点却没有，那么该节点就是最低的公共祖先。
 * 辅助内存？
 * 用两个链表分别保存从根节点到输入的两个节点的路径，然后把问题转换成两个链表的最后公共节点。
 *
 *
 */
public class Q68_树中两个节点的最低公共祖先 {
}