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

题目：

输入一棵树的根节点，输入两个被观察节点，求这两个节点的最低(最近)公共祖先。

分析：

1. 假设是二叉搜索树（二叉搜索树是一个排序的二叉树，左子树的结点小于根结点，右子树的结点大于根结点），故找到一个结点，使其大于左子结点小于右子结点即可。

   public static BinaryTreeNode getLastCommonNode1(BinaryTreeNode pRoot, BinaryTreeNode pLeft, BinaryTreeNode pRight) {
       BinaryTreeNode treeNode = null;
       if (pRoot == null || pLeft.value > pRight.value) {
           return null;
       }
       if (pRoot.value >= pRight.value) {
           // 说明根节点没有右子树，要到它的左子树查找
           treeNode = getLastCommonNode1(pRoot.left, pLeft, pRight);
       }
       if (pRoot.value <= pLeft.value) {
           // 说明根节点没有左子树，要到它的右子树查找
           treeNode = getLastCommonNode1(pRoot.right, pLeft, pRight);
       }
       if (pRoot.value >= pLeft.value && pRoot.value <= pRight.value) {
           return pRoot;
       }
       return treeNode;
   }
   

2. 假设是普通的二叉树。递归遍历找到所给定的两个结点，然后向上标记，直到有一个结点的左子结点和右子结点都不为空返回即可。

   public static BinaryTreeNode getLastCommonNode2(BinaryTreeNode pRoot, BinaryTreeNode pLeft, BinaryTreeNode pRight) {
       // 发现目标节点则通过返回值标记该子树发现了某个目标结点
       if (null == pRoot || pRoot == pLeft || pRoot == pRight) {
           return null;
       }
       // 查看左子树中是否有目标结点，没有为null
       BinaryTreeNode left = getLastCommonNode2(pRoot.left, pLeft, pRight);
       // 查看右子树是否有目标节点，没有为null
       BinaryTreeNode right = getLastCommonNode2(pRoot.right, pLeft, pRight);
       // 都不为空，说明左右子树都有目标结点，则公共祖先就是本身
       if (left != null && right != null) {
           return pRoot;
       }
       // 如果发现了目标节点，则继续向上标记为该目标节点
       return left == null ? right : left;
   }
   

3. 假设是普通的树，但是每个子结点都有指向父结点的指针，这样的话类似与前面的链表找公共结点一样。

4. 假设就是一棵普通的数，子结点没有指向父结点的指针。

   获取从根节点分别到两条节点的路径，求这两条路径的最小公共节点

   public static TreeNode getLastCommonNode3(TreeNode pRoot, TreeNode p1, TreeNode p2) {
       // 保存p1的路径
       List<TreeNode> path1 = new ArrayList<>();
       // 保存p2的路径
       List<TreeNode> path2 = new ArrayList<>();
       List<TreeNode> tmpList = new ArrayList<>();
       getNodePath(pRoot, p1, tmpList, path1);
       getNodePath(pRoot, p2, tmpList, path2);
       // 如果路径不存在，返回空
       if (path1.isEmpty() || path2.isEmpty()) {
           return null;
       }
       return getLastCommonParent(path1, path2);
   }
   
   private static void getNodePath(TreeNode pRoot, TreeNode pNode, List<TreeNode> tmpList, List<TreeNode> path) {
   
       if (null == pRoot || pRoot == pNode) {
           return;
       }
       tmpList.add(pRoot);
       List<TreeNode> children = pRoot.children;
       for (TreeNode child : children) {
           if (child == pNode) {
               path.addAll(tmpList);
               break;
           }
           getNodePath(child, pNode, tmpList, path);
       }
       tmpList.remove(tmpList.size() - 1); // 清空集合
   }
   
   private static TreeNode getLastCommonParent(List<TreeNode> path1, List<TreeNode> path2) {
       TreeNode tempNode = null;
       for (int i = 0; i < path1.size(); i++) {
           if (path1.get(i) == path2.get(i)) {
               tempNode = path1.get(i);
           }
       }
       // 循环结束时tmpNode即为最后一个共同结点
       return tempNode;
   }