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()); } }; ~~~ **四. 小结** 与前面一题一样,该题考察了基础概念,并不涉及过多的算法问题。
';