Construct Binary Tree from Inorder and Postorder Traversal
最后更新于：2022-04-01 22:57:40
**一. 题目描述**
Given inorder and postorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
**二. 题目分析**
这道题和Construct Binary Tree from Preorder and Inorder Traversal类似，都是考察基本概念的，后序遍历是先遍历左子树，然后遍历右子树，最后遍历根节点。
做法都是先根据后序遍历的概念，找到后序遍历最后的一个值，即为根节点的值，然后根据根节点将中序遍历的结果分成左子树和右子树，然后就可以递归的实现了。
上述做法的时间复杂度为`O(n^2)`，空间复杂度为`O(1)`。
**三. 示例代码**
~~~
#include
#include
#include
using namespace std;
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution
{
private:
TreeNode* buildTree(vector::iterator PostBegin, vector::iterator PostEnd,
vector::iterator InBegin, vector::iterator InEnd)
{
if (InBegin == InEnd)
{
return NULL;
}
if (PostBegin == PostEnd)
{
return NULL;
}
int HeadValue = *(--PostEnd);
TreeNode *HeadNode = new TreeNode(HeadValue);
vector::iterator LeftEnd = find(InBegin, InEnd, HeadValue);
if (LeftEnd != InEnd)
{
HeadNode->left = buildTree(PostBegin, PostBegin + (LeftEnd - InBegin),
InBegin, LeftEnd);
}
HeadNode->right = buildTree(PostBegin + (LeftEnd - InBegin), PostEnd,
LeftEnd + 1, InEnd);
return HeadNode;
}
public:
TreeNode* buildTree(vector& inorder, vector& postorder)
{
if (inorder.empty())
{
return NULL;
}
return buildTree(postorder.begin(), postorder.end(), inorder.begin(),
inorder.end());
}
};
~~~
**四. 小结**
与前面一题一样，该题考察了基础概念，并不涉及过多的算法问题。
';