左神算法--寻找二叉树的最低公共祖先

题目：给定二叉树root的两个节点node1和node2，找到他们的最低公共祖先节点

方式1：
将二叉树每个节点的父节点找出来并使用hashmap保存，
将node1节点到root节点的路线保存到一个hsahset中
node2利用保存父节点的hashmap向上遍历，如果遇到了hashset中有的节点，那就是公共祖先节点

//建立父节点映射hshmap
void process(BTree * node,unordered_map<BTree *,BTree *> & fathers)
{
    if (node->left==NULL&&node->right==NULL)
    return;
    if(node->left!=NULL)
    {
        fathers.insert(make_pair(node->left,node));
        process(node->left,fathers);
    }
    if(node->right!=NULL)
    {
        fathers.insert(make_pair(node->right,node));
        process(node->right,fathers);
    }
    return;

}
BTree * LCA_traditional(BTree * node,BTree * node1,BTree * node2)
{
    unordered_map<BTree *,BTree *>fathers;
    unordered_set<BTree *>node1_;
    fathers.insert(make_pair(node,node));
    process(node,fathers);
    //建立node1到root的hashset
    while(1)
    {
        node1_.insert(node1);
        node1=fathers[node1];
        if(fathers[node1]==node1)
        break;
    }
    //node2向上遍历寻找
    while(node1_.find(node2)==node1_.end())
    {
        node2=fathers[node2];
    }
    return node2;
}

方式二：
这个方式是一个层层递进的方式，从根节点开始一层层向下遍历，遇到node1或者node2，或者空就对应返回node1或者node2，或者空。如果都没有就接着往下遍历，直到找到这几个，开始返回，返回的时候左不为空就返回左，右不为空就返回右，都为空就返回空，如果发现都不为空，那就是找到最近公共祖先了。因为是递归的返回这样每次返回得到的左右节点都是在同一根节点的左右节点，因此node1和node2的深度不同这个问题就被解决了。非常巧妙

BTree * LCA(BTree * node,BTree * node1,BTree * node2)
{
    if(node==node1||node==node2||node==NULL)
    return node;
    BTree * left_=new BTree;
    BTree * right_=new BTree;
    left_=LCA(node->left,node1,node2);
    right_=LCA(node->right,node1,node2);
    if(left_!=NULL&&right_!=NULL)
    return node;
    return left_!=NULL?left_:right_;
}