트리에 있는 두 노드의 가장 가까운 공통 부모 노드를 찾습니다

1741 단어
경전을 비교하는 문제는 주로 두 가지 사고방식이 있는데 하나는 순수한 귀속이다.또 하나는 각 노드에서 루트까지의 경로를 찾은 다음에 두 개의 경로의 공공 노드를 구하는 것이다.
경로를 찾는 코드를 붙여라: 귀속적인 사고방식이기도 하다
// , 、 、 。
#include <iostream>
#include <stack>

using namespace std;

struct TreeNode 
{
	int value;
	TreeNode *pLeft;
	TreeNode *pRight;
};

void addTreeNode(TreeNode *&pRoot,int *index,int &iCurrent){
	if(-1 != index[iCurrent]){
		TreeNode *pCurrent = new TreeNode;
		pCurrent->value = index[iCurrent++];
		pCurrent->pLeft = NULL;
		pCurrent->pRight = NULL;
		pRoot = pCurrent;

		addTreeNode(pRoot->pLeft,index,iCurrent);
		addTreeNode(pRoot->pRight,index,iCurrent);
	}else{
		++iCurrent;
	}
}

void createTree(TreeNode *&pRoot,int *index){
	int iCurrent = 0;
	addTreeNode(pRoot,index,iCurrent);
}

bool findA(TreeNode *pRoot,int value,stack<TreeNode*> &s){
	if(pRoot ==NULL){
		return false;
	}
	if(pRoot->value == value){
		s.push(pRoot);
		return true;
	}else if(findA(pRoot->pLeft,value,s)){
		s.push(pRoot);
		return true;
	}else if(findA(pRoot->pRight,value,s)){
		s.push(pRoot);
		return true;
	}
	return false;
}

void preOrder(TreeNode *pRoot){
	if(pRoot != NULL){
		cout << pRoot->value << " ";
		preOrder(pRoot->pLeft);
		preOrder(pRoot->pRight);
	}
}

int main(){
	int index[] = {8,6,5,-1,-1,-1,10,11,-1,-1,-1};// 
	TreeNode *pRoot = NULL;

	createTree(pRoot,index);// 
/*
         8
        / \
       6   10
      /    /
     5    11
*/
	preOrder(pRoot);
	stack<TreeNode*> s;
	bool ret = findA(pRoot,11,s);
	cout << endl;
	if(ret){
		while(!s.empty()){
			cout << s.top()->value << " ";
			s.pop();
		}
		cout << endl;
	}
	

	return 1;
}

좋은 웹페이지 즐겨찾기