一 前序和中序还原二叉树
思路是这样的：
这个算法的目的是根据前序遍历和中序遍历的结果，重建一棵二叉树。
前序遍历的特点是，第一个元素一定是根节点，后面的元素是左子树和右子树的前序遍历。
中序遍历的特点是，根节点在左子树和右子树的中间，左边的元素是左子树的中序遍历，右边的元素是右子树的中序遍历。
因此，我们可以利用前序遍历确定根节点，然后在中序遍历中找到根节点的位置，从而分割出左子树和右子树的区间。
然后，我们递归地对左子树和右子树进行同样的操作，直到区间为空或者只有一个元素为止。
最后，我们返回重建好的二叉树的根节点。
代码并加上了注释：
class Solution { public: //后序确定根 //中序分割左右区间 TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int& posti, int ibegin, int iend) { if (ibegin > iend) return nullptr; //如果中序区间为空，返回空指针 TreeNode* root = new TreeNode(postorder[posti]); //创建根节点，值为后序遍历的最后一个元素 //分割左右子区间 int rooti = ibegin; //找到根节点在中序遍历中的位置 while (rooti <= iend) { if (inorder[rooti] == postorder[posti]) break; //找到了，跳出循环 else rooti++; //没找到，继续向右移动 } --posti; //后序遍历的索引向前移动一位 root->right = _buildTree(inorder, postorder, posti, rooti+1, iend); //递归构建右子树，中序区间为[rooti+1, iend] root->left = _buildTree(inorder, postorder, posti, ibegin, rooti-1); //递归构建左子树，中序区间为[ibegin, rooti-1] return root; //返回根节点 } TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { int i = postorder.size()-1; //初始化后序遍历的索引为最后一位 return _buildTree(inorder, postorder, i, 0, inorder.size()-1); //调用辅助函数，中序区间为[0, inorder.size()-1] } };
二 后序和中序还原二叉树
如果是后序和中序让你来还原二叉树呢？
还是上面那种思路，只不过这次要先递归构建右子树，这是因为后序遍历的特点是，最后一个元素是根节点，前面的元素是左子树和右子树的后序遍历，而且右子树在左子树的后面。所以，我们要先递归构建右子树，然后再构建左子树，这样才能保证后序遍历的索引正确。
后序遍历的最后一个元素是二叉树的根节点。
在中序遍历中找到根节点的位置，根节点左边的序列是左子树的中序遍历，右边的序列是右子树的中序遍历。
在后序遍历中找到对应的左子树和右子树的序列，左子树的长度和中序遍历中左子树的长度相同，右子树也一样。
递归地对左子树和右子树重复上述步骤，直到后序遍历或中序遍历为空。
例如，给定后序遍历 [9, 15, 7, 20, 3] 和中序遍历 [9, 3, 15, 20, 7]，还原二叉树的过程如下：
后序遍历的最后一个元素是 3，它是二叉树的根节点。
在中序遍历中找到 3 的位置，它左边的序列 [9] 是左子树的中序遍历，右边的序列 [15, 20, 7] 是右子树的中序遍历。
在后序遍历中找到对应的左子树和右子树的序列，左子树只有一个元素 [9]，右子树有三个元素 [15, 7, 20]。
对左子树递归地还原二叉树，由于后序遍历和中序遍历只有一个元素，所以左子节点就是 9。
对右子树递归地还原二叉树，由于后序遍历和中序遍历都不为空，重复上述步骤。
代码：
class Solution { public: //后序确定根 //中序分割左右区间 TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int& posti, int ibegin, int iend) { if (ibegin > iend) return nullptr; //如果中序区间为空，返回空指针 TreeNode* root = new TreeNode(postorder[posti]); //创建根节点，值为后序遍历的最后一个元素 //分割左右子区间 int rooti = ibegin; //找到根节点在中序遍历中的位置 while (rooti <= iend) { if (inorder[rooti] == postorder[posti]) break; //找到了，跳出循环 else rooti++; //没找到，继续向右移动 } --posti; //后序遍历的索引向前移动一位 root->right = _buildTree(inorder, postorder, posti, rooti+1, iend); //递归构建右子树，中序区间为[rooti+1, iend] root->left = _buildTree(inorder, postorder, posti, ibegin, rooti-1); //递归构建左子树，中序区间为[ibegin, rooti-1] return root; //返回根节点 } TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { int i = postorder.size()-1; //初始化后序遍历的索引为最后一位 return _buildTree(inorder, postorder, i, 0, inorder.size()-1); //调用辅助函数，中序区间为[0, inorder.size()-1] } };
本节完
