[leetcode] 106. Construct Binary Tree from Inorder and Postorder Traversal（medium）

原题地址

思路： 和leetcode105题差不多，这道题是给中序和后序，求出二叉树。

解法一：

思路和105题差不多，只是pos是从后往前遍历，生成树顺序也是先右后左。

class Solution { public: TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) { int pos = postorder.size() - 1; return dfs(inorder, postorder, 0, inorder.size(), pos); } private: TreeNode *dfs(vector<int> &inorder, vector<int> &postorder, int beg, int end, int &pos) { TreeNode *node = NULL; if (beg < end) { int i = 0; for (i = beg; i < end; ++i) if (postorder[pos] == inorder[i]) break; pos--; node = new TreeNode(inorder[i]); node->right = dfs(inorder, postorder, i + 1, end, pos); node->left = dfs(inorder, postorder, beg, i, pos); } return node; } };

解法二：

解法二是看了别人的题解入手的，和解法一不同思路的是对两个序都用一组beg和end来划分区间。 中序（beg,end）很好划分，假设mid指向当前节点的root值，则分为mid前一半和mid后一半。 后序（pbeg,pend）的划分，是mid - beg的这一段距离。

class Solution { public: TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) { return dfs(inorder, postorder, 0, inorder.size(), 0, postorder.size()); } private: TreeNode *dfs(vector<int> &inorder, vector<int> &postorder, int beg, int end, int pbeg, int pend) { TreeNode *node = NULL; if (beg < end) { int i = 0; for (i = beg; i < end; ++i) if (postorder[pend - 1] == inorder[i]) break; node = new TreeNode(inorder[i]); node->left = dfs(inorder, postorder, beg, i, pbeg, pbeg + i - beg); node->right = dfs(inorder, postorder, i + 1, end, pbeg + i - beg, pend - 1); } return node; } };

解法一好理解，但是速度慢，用了16ms，击败46% 解法二难点在于理解后序区间划分的依据，用了12ms，击败78%

虽然做了105题，但是做这题还是花了一个半小时。 还是因为不够深入的理解原理，不能总是光看题解就过了。

转载于:https://www.cnblogs.com/ruoh3kou/p/9893446.html