//原文：
//
// Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.
//
// 译文：
//
// 写程序在一棵二叉树中找到两个结点的第一个共同祖先。不允许存储额外的结点。注意： 这里不特指二叉查找树。
//
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <list>
using namespace std;
struct treenode
{
char data;
treenode * left;
treenode * right;
treenode * parent;
};
class tree
{
public:
tree()
{
//root = create();
root = NULL;
}
~tree()
{
/***清空二叉树***/
}
/***二叉排序树：插入。***/
void insert(char *s)
{
if (s == NULL)
{
return;
}
int size = strlen(s);
for (int i = 0; i<size; i++)
{
insert(&root, s[i], NULL);
}
}
void levelOrder()
{
queue<treenode *> q;
if (root != NULL)
{
q.push(root);
}
while(!q.empty())
{
treenode *t = q.front();
cout<<t->data<<endl;
q.pop();
if (t->left != NULL)
{
q.push(t->left);
}
if (t->right != NULL)
{
q.push(t->right);
}
}
}
treenode * findNext(treenode *p)
{
if (p->right == NULL)
{
return p->parent;
}
else
{
treenode *s = p->right;
while(s->left != NULL)
{
s = s->left;
}
return s;
}
}
void preOrder(){ pOrder(root);}
void inOreder(){ zOrder(root);}
void postOreder(){ hOrder(root);}
treenode *root;
void findLCA(treenode *p,treenode *n1,treenode *n2,treenode **lca)
{
if (p==NULL || n1 ==NULL || n2 == NULL)
{
return;
}
if (p && father(p,n1) && father(p,n2))
{
*lca = p;
findLCA(p->left,n1,n2,lca);
findLCA(p->right,n1,n2,lca);
}
}
private:
/***判断b是否为fa的子孙***/
bool father(treenode * fa, treenode * b)
{
if (fa == NULL)
{
return false;
}
else if (fa == b)
{
return true;
}
else
{
return father(fa->left,b)||father(fa->right,b);
}
}
void insert(treenode **p, char s, treenode *parent)
{
if (((*p) == NULL) && s != '\0')
{
*p = new treenode;
(*p)->data = s;
(*p)->left = NULL;
(*p)->right = NULL;
(*p)->parent = parent;
}
else
{
if ((*p)->data > s)
{
insert(&((*p)->left) , s, *p);
}
else
{
insert(&((*p)->right) , s, *p);
}
}
}
void pOrder(treenode *p)
{
if (p==NULL)
{
return;
}
cout<<p->data<<" "<<endl;
pOrder(p->left);
pOrder(p->right);
}
void zOrder(treenode *p)
{
if (p==NULL)
{
return;
}
zOrder(p->left);
cout<<p->data<<" "<<endl;
zOrder(p->right);
}
void hOrder(treenode *p)
{
if (p==NULL)
{
return;
}
hOrder(p->left);
cout<<p->data<<" "<<endl;
hOrder(p->right);
}
};
int main()
{
/**非递归层次遍历*************************/
tree s;
char t[8] = "3289654";
s.insert(t);
//s.levelOrder();
//treenode *p =s.findNext((s.root)->right);
//cout<<p->data<<endl;
treenode *lca;
s.findLCA(s.root, s.root->right->right,s.root->right->left->left,&lca);
cout<<lca->data<<endl;
return 0;
}