山东德州如何网站建设教程/网游推广员

情况3：也是最普通的情况，二叉树是普通的二叉树，节点只有left/right，没有parent指针。

                                          10/       /6         14/  /       /　  /4   8   12 　 16/  /3   5

基本思想：记录从根找到node1和node2的路径，然后再把它们的路径用类似的情况一来做分析，比如还是node1=3,node2=8这个case.我们肯定可以从根节点开始找到3这个节点，同时记录下路径3,4,6,10，类似的我们也可以找到8,6,10。我们把这样的信息存储到两个vector里面，把长的vector开始的多余节点3扔掉，从相同剩余长度开始比较，4!=8, 6==6,我们找到了我们的答案。

#include<iostream>
#include<vector>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
//int re = 0;
struct bstNode
{bstNode *pLeft,*pRight;int value;
};
void createTree(bstNode *&pRoot)//创建任意二叉树代码
{bstNode *root = pRoot;int val = 0;    cin >> val;if (val == -1)root = NULL;else{pRoot = (bstNode *)malloc(sizeof(bstNode));pRoot->value = val;createTree(pRoot->pLeft);createTree(pRoot->pRight);  }
}
void preOrder(bstNode *&p)
{if (p != NULL){cout << p->value<<" ";preOrder(p->pLeft);preOrder(p->pRight);}
}
bool findPath(bstNode *pRoot,int val,vector<bstNode *> &path)//从树根到指定节点路径的求法
{if (pRoot == NULL) return false;if (pRoot->value != val){if (findPath(pRoot->pLeft,val,path)){path.push_back(pRoot);return true;}else{if (findPath(pRoot->pRight,val,path)){path.push_back(pRoot);return true;}else{return false;}}}else{path.push_back(pRoot);return true;}
}
bstNode *lcas(bstNode *pRoot,int val1,int val2)//核心代码，求最近公共祖先,这里的返回值没有问题
{vector<bstNode *> path1;vector<bstNode *> path2;bool find = false;bstNode *pResult = NULL;find |= findPath(pRoot,val1,path1);find &= findPath(pRoot,val2,path2);if (find){int min = path1.size()>path2.size()?path2.size():path1.size();int len1 = path1.size()-min;int len2 = path2.size()-min;for(;len1 < path1.size(),len2<path2.size();len1++,len2++)//这里的处理非常巧妙.从相同剩余长度开始比较{if (path1[len1] == path2[len2]){cout << path1[len1]->value;pResult = path1[len1];break;}}}   return pResult;
}
void destroy(bstNode *pRoot)//销毁二叉树
{if(pRoot == NULL) return;destroy(pRoot->pLeft);destroy(pRoot->pRight);free(pRoot);
}
int main()
{bstNode *pRoot = NULL;createTree(pRoot);preOrder(pRoot);int val1 = 0,val2 = 0;cin >> val1;cin >> val2;lcas(pRoot,val1,val2);//cout << result<<endl;destroy(pRoot);return 0;
}

运行结果如下：(centos5.5)
[root@localhost c++]# ./a.out
10 6 4 3 -1 -1 -1 8 5 -1 -1 -1 14 12 -1 -1 16 -1 -1
10 6 4 3 8 5 14 12 16
6 4
6[root@localhost c++]#
有递归可知：
这里path1[]->value = {6,10};(0-path1.size()-1)
path2[]->value = {4,6,10};(0-path2.size()-1);