剣指offer-二叉木

【04二叉木の再建】
タイトルの説明
ツリーの前順および中順の結果を入力し、ツリーを再構築します.入力された前シーケンスおよび中シーケンスの結果に重複する数値が含まれていないと仮定します.例えば、前シーケンス遍歴シーケンス{1,2,4,7,3,5,6,8}と中シーケンス遍歴シーケンス{4,7,2,1,5,3,8,6}を入力すると、ツリーが再構築され、戻ります.
考え方:
1)二叉木の構築,付与,左右の子木の利便性?2)前順リスト,中順リストから左右のサブツリーを復元する:前順のルート,中順で左右のサブツリーを分割し,左右のサブツリーを再帰的に再構成する3)C++未知長の配列を読み出し,配列終了をリターンイン判定する
サンプル:
1 2 4 7 3 5 6 8 4 7 2 1 5 3 8 6

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* reConstructBinaryTree(vector pre,vector vin) {	
//           ，     。                             
    if(pre.empty()||vin.empty())
		return NULL;
	if(pre.size()!=vin.size())
		return NULL;
		
	TreeNode *p;
 	p = (TreeNode*)malloc(sizeof(TreeNode));
    int i=0,mid=0;
    for(i=0;i pre_left,pre_right,vin_left,vin_right;
	for(i=0;ival = pre[0];
    p->left = reConstructBinaryTree(pre_left,vin_left);
    p->right = reConstructBinaryTree(pre_right,vin_right);
	return p;
}

【17木のサブ構造】
タイトルの説明
2本の二叉木A,Bを入力し,BがAのサブ構造であるか否かを判断する.(ps:空の木は任意の木のサブ構造ではないと約束しました)
考え方:
1)まず,AとBが同じ木であるか否かを再帰的に判断する.そうでなければ左サブツリーまたは右サブツリーとBが同じツリーであるかどうかを判断する2)2つのツリーが同じツリーであるかどうかを再帰的に判断する:判断する各ノードが同じであるかどうかを判断する

bool SameTree(TreeNode* pRoot1, TreeNode* pRoot2)    //                  
{
	bool val;
	if(pRoot2==NULL)
		return true;
	if(pRoot1==NULL)
		return false;
	if(pRoot1->val!=pRoot2->val)
		return false;
	else
		return SameTree(pRoot1->left,pRoot2->left) && SameTree(pRoot1->right,pRoot2->right);
}
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)  //     	    2       1     
{
	bool val = false;
	if(pRoot1==NULL ||pRoot2==NULL)
		return val;
	return SameTree(pRoot1,pRoot2) | HasSubtree(pRoot1->left,pRoot2) || HasSubtree(pRoot1->right,pRoot2);
}

【18ツリーのミラー】
タイトルの説明
指定したツリーを操作し、ソースツリーのミラーに変換します.
説明を入力:

        ：     
    	    8
    	   /  \
    	  6   10
    	 / \  / \
    	5  7 9 11
    	     
    	    8
    	   /  \
    	  10   6
    	 / \  / \
    	11 9 7  5

考え方:
1)左右のサブツリーを再帰的に反転2)非再帰的に反転し,スタックを利用してノードに格納する.

void Mirror(TreeNode *pRoot)		//            
{
	TreeNode *p; 
	if(pRoot==NULL)
	{
		return;
	}
	else{
		p= pRoot->left;
		pRoot->left = pRoot->right;
		pRoot->right = p;
		Mirror(pRoot->left);
		Mirror(pRoot->right);
		//cout<left->val<right->val< s;			//         。            
	s.push(pRoot);
	while(!s.empty())
	{
		TreeNode *p = s.top();				
		cout<val<left; 
		p->left = p->right;
		p->right = tmp;
		if(p->left!=NULL)
		{
			s.push(p->left);
			cout<val<left->val<right!=NULL){
			s.push(p->right);
			cout<val<right->val<

【22二叉木を上から下まで印刷】
タイトルの説明
ツリーの各ノードを上から下に印刷し、同レイヤノードを左から右に印刷します.
考え方:
1)キューストレージノードの利用

vector PrintFromTopToBottom(TreeNode* root) {  //           
	queue q;
	vector result;
	if(root)
		q.push(root);
	while(!q.empty())
	{
		TreeNode* cur = q.front();
		q.pop();
		result.push_back(cur->val);
		if(cur->left)
		{
			q.push(cur->left);
		}
			
		if(cur->right)
		{
			q.push(cur->right);
		}
	}
	return result;
}

【23二叉木の後序遍歴】
タイトルの説明
整数配列を入力し、その配列が二叉探索ツリーの後順に遍歴した結果であるかどうかを判断します.もしそうであればYesを出力し、そうでなければNoを出力します.入力された配列の任意の2つの数字が互いに異なると仮定します.

bool VerifySquenceOfBST(vector s) {
	if(s.size()==1)   
		return true;
	if(s.size()==0)   		//     ，[]                
		return false;
	int mid=0,end = s.size()-1, i=0;
	while(mid left,right;
	for(i=0;i