3-31：还原二叉树

问题：还原二叉树

（1）根据一个二叉树的前序遍历和中序遍历还原二叉树。 （2）根据一个二叉树的后序遍历和中序遍历还原二叉树。

#include<iostream>
#include<list>
using namespace std;
typedef list<int>::iterator index;
class TreeNode
{
public:
	TreeNode(int value, TreeNode* left = NULL, TreeNode * right = NULL)
		:ivalue(value), ileft(left), iright(right)
	{

	}
	int getvalue()
	{
		return ivalue;
	}
	TreeNode* getleft()
	{
		return ileft;
	}
	TreeNode* getright()
	{
		return iright;
	}
	void setleft(TreeNode* left)
	{
		ileft = left;
	}
	void setright(TreeNode* right)
	{
		iright = right;
	}
private:
	int ivalue;
	TreeNode* ileft;
	TreeNode* iright;
};
void fronttraversal(list<int> &frontsequence,TreeNode* root)
{
	if (root)
	{
		frontsequence.push_back(root->getvalue());
		fronttraversal(frontsequence,root->getleft());
		fronttraversal(frontsequence,root->getright());
	}	
}
void middletraversal(list<int> &frontsequence, TreeNode* root)
{
	if (root)
	{
		middletraversal(frontsequence, root->getleft());
		frontsequence.push_back(root->getvalue());
		middletraversal(frontsequence, root->getright());
	}
}
TreeNode* reconstruct(index frontstart, index frontend, index middlestart, index middleend)
{
	TreeNode* root = new TreeNode(*frontstart);
	if (frontstart == frontend && *frontend == *frontstart)
		return root;
	index rootposition= middlestart;
	int leftlength = 0;
	index newfrontstart = frontstart;
	while (rootposition != middleend && *rootposition != root->getvalue())
	{
		leftlength++;
		newfrontstart++;
		rootposition++;
	}
	if (*rootposition == root->getvalue())
	{
		if (leftlength > 0)
		{
			root->setleft(reconstruct(++frontstart, add(frontstart,leftlength), middlestart, --rootposition));
			rootposition++;
		}
		if (rootposition != middleend)
		{
			root->setright(reconstruct(++add(frontstart,leftlength), frontend, ++rootposition, middleend));
		}
	}

}
int main()
{
	TreeNode* node7 = constructatree();
	
	list<int> frontsequence = list<int>();
	fronttraversal(frontsequence, node7);
	list<int> middlesequence = list<int>();
	middletraversal(middlesequence, node7);
	
	TreeNode* node1 = reconstruct(frontsequence.begin(), --frontsequence.end(), middlesequence.begin(), --middlesequence.end());

}

避免返回handles指向对象内部的成分

突然想到effective C++中提到过避免返回handles指向对象内部的成分，在上面的代码中尽管iright和ileft是私有成员，但是通过getleft和getright返回的reference却能够用来更改他们，所以这两个数据成员实际上是public，是时候加上const了。

const int getvalue() const
const TreeNode* getleft() const
const TreeNode* getright() const
void fronttraversal(list<int> &frontsequence,const TreeNode* root)
void middletraversal(list<int> &frontsequence, const TreeNode* root)