二叉樹の最近のパブリックノード

二叉ツリーでは、2つのサブノードの最近のパブリック親ノードが検索される.実装方法:まず、各サブノードのパスを見つけ、その後、2つの経路の最後の同じノードを比較し、最近のパブリック親ノードである.
二叉樹のデータ構造は以下の通りです.

typedef struct _node
{
	char data;
	struct _node* lchild;
	struct _node* rchild;
}node;

サブノードのパスを検索し、リンクリストリストリストリストリストを利用して実現する.

bool findNodePath(node* root, char elem, list<node*> &path)
{
	if (!root) return false;
	path.push_back(root);
	if (elem==root->data) return true;
	if(findNodePath(root->lchild,elem,path)) return true;
	if(findNodePath(root->rchild,elem,path)) return true;
	path.pop_back();
	return false;
}

上記のfindNodePath関数を利用すれば、最近のパブリックノードが得られやすくなります.

node* findNearestParent(node* root, char elem1, char elem2) 
{
	list<node*> path1,path2;
	if (findNodePath(root,elem1,path1)&&findNodePath(root,elem2,path2))
	{
		list<node*>::iterator iter1=path1.begin();
		list<node*>::iterator iter2=path2.begin();
		while(*iter1==*iter2)
		{
			iter1++;
			iter2++;
		}
		return *(--iter1);
	}
	return NULL;
}