LCA based on array store
之前看过剑指Offer分析LCA问题，对于各种情况都要考虑。
这次是顺序存储的完全二叉树，计算i j结点的最短路径，其实也是LCA的应用。i j二进制位运算的共同前缀就是结果了，结点是1-based的index，
x^y得到前缀部分都是0，前缀是上面公共的部分，上限(x^y)=z,得到后面不相同的部分的位数，然后将x>>z就得到x y的LCA，如果两个节点不是祖孙关系的话。
然后处理一下，计算得到LCA和x y的分别距离加起来。
如果是祖孙关系，就是直接计算。
后来发现不知道怎么判断是否是祖孙关系，后来看了Ahdoc大神代码，发现还是可以统一到一起处理。还是要和之前两个链表的首个公共节点一样处理。
要先把两个推到同一层，然后再计算LCA，最后的距离是log2(x)+log2(y)-2*log2(z), z是x y的LCA，这样可以将两种情况统一到一起处理。
今天看到群里讨论placement new 的语法，也就是先申请一块空间，然后定位new的方式，将指针指向这块内存，但是似乎最后destructor的时候
不会释放这块空间。
http://www.cnblogs.com/weiweiqiao99/archive/2012/06/16/2545710.html
今天看到JulyEdu又有人问，我又写了一遍，这一次似乎理解更进一步了。
这道题目的递归算法是经典算法，但是我第一遍看的时候始终不得其解，今天记录下一些理解后的心得。
时间O(N), 空间O(1)似乎面试都不算系统栈空间
struct Node
{
int val;
Node* left, *right;
};
Node* LCA(Node*root, Node* p1, Node*p2)
{// p1&&p2, p1!=p2, p1 p2 in tree
if(!root) return NULL;
if(root==p1 || root==p2) return root;
Node* leftLCA=LCA(root->left, p1, p2);
Node* rightLCA=LCA(root->right, p1, p2);
if(leftLCA && rightLCA) return root;
else if(leftLCA && !rightLCA) return leftLCA;
else if(rightLCA && !leftLCA) return rightLCA;
else return NULL;
}
他的递归结构是指，对于左子树去找到p1或者p2, 右子树也是如此，第一次遇到其中一个节点就返回，如果第一次左右子树 分别都能找到p1 或者p2,
那么必然p1 p2 分别在左右子树，则此时root就是LCA(因为不可能左右子树同时找到p1或者p2)，如果一颗子树找到，说明结果就在一颗子树那里，
如果都没有的话，说明找不到LCA，可能root空，或者p1 p2有空的，等等。