前言
RMQ： 数组 a0, a1, a2,..., an-1, 中求随意区间 a[i+1], a[i+2], ..., a[i+k] 的最小值
LCA： 求二叉树中两个节点的最低公共祖先
本文将证明这两个问题能够相互归约为还有一个问题。
证明
先通过一个简单的样例来说明问题。见下图：
求 [7 2 8 6] 的最小值 2，等价于求二叉树中节点 7 和 节点6的 LCA，也就是 节点2。
有意思吧。。。
一、 RMQ -> LCA
给定一个数组，怎样求出其对于的二叉树呢？？
方法1： 这棵二叉树事实上具有类似最小堆的性质（尽管不是全然二叉树），
能够採用递归建树，先找到最小值作为 root 节点，然后对最小值左半边和右半边递归建左子树和右子树就可以。
复杂度： 最好 O(NlgN)，最坏 O(N^2), 分析类似与快排。。
方法2：因此扫描数组的每个元素，将元素按例如以下规则插入树中；
从根节点出发，一直往右孩子移动，直到当前插入元素值位于一个 父亲节点和右孩子节点之间。
将插入节点作为 父亲节点的右孩子，之前的右子树作为插入节点的左子树。
二、LCA -> RMQ
怎样将一个 LCA 归约到一个数组求区间最小值呢？？ 这个问题有一个 trick.
增加我们的二叉树例如以下图，注意，它并不满足最小堆的性质！！！
1. 做一个变换，将节点的值改成节点的深度，这样，新的二叉树就满足了最小堆的性质；
这两颗树的节点是一一相应的，
求 LCA(node3, node8) 相应于 在新树中求 LCA(node3, node1)
2. 新树中求 LCA(node3, node1) 相应于在新树的中序遍历序列 2 1 3 2 0 1 中求 【3 2 0 1】的最小值；
