首页 > 代码库 > [Leetcode][Tree][Construct Binary Tree from Preorder/Postorder and Inorder Traversal ]
[Leetcode][Tree][Construct Binary Tree from Preorder/Postorder and Inorder Traversal ]
从树的中序遍历+前/后序遍历重建一棵树。
必须使用iterator才能过，否则会MLE。
1、preorder + inorder
第一个版本，使用坐标范围：
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 public:12 TreeNode *build(vector<int> &preorder, int startPre, int endPre,13 vector<int> &inorder, int startIn, int endIn) {14 if (startPre >= preorder.size() || endPre > preorder.size() 15 || startIn >= inorder.size() || endIn > inorder.size()16 || startPre >= endPre || startIn >= endIn) {17 return NULL;18 } 19 TreeNode *root = new TreeNode(0);20 int pos = -1;21 for (int i = startIn; i < endIn; i++) {22 if (inorder[i] == preorder[startPre]) {23 pos = i - startIn;24 break;25 }26 }27 if (pos == -1) {28 return NULL;29 } else {30 //vector<int> preLeft(preorder.begin() + 1, preorder.begin() + pos + 1);31 //vector<int> preRight(preorder.begin() + pos + 1, preorder.end());32 //vector<int> inLeft(inorder.begin(), inorder.begin() + pos);33 //vector<int> inRight(inorder.begin() + pos + 1, inorder.end());34 root->val = inorder[pos + startIn];35 root->left = build(preorder, startPre + 1, startPre + pos + 1, inorder, startIn, startIn + pos);36 root->right = build(preorder, startPre + pos + 1, endPre, inorder, startIn + pos + 1, endIn);37 }38 return root;39 }40 TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {41 return build(preorder, 0, preorder.size(), inorder, 0, inorder.size());42 }43 };
第二个版本，使用迭代器：
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 public:12 typedef vector<int>::iterator Iter;13 TreeNode *build(Iter preBegin, Iter preEnd, Iter inBegin, Iter inEnd) {14 if (preBegin == preEnd || inBegin == inEnd) {15 return NULL;16 } 17 TreeNode *root = new TreeNode(0);18 Iter target = find(inBegin, inEnd, *preBegin);19 int pos = target - inBegin;20 if (target == inEnd || pos < 0) {21 return NULL;22 } else {23 //vector<int> preLeft(preorder.begin() + 1, preorder.begin() + pos + 1);24 //vector<int> preRight(preorder.begin() + pos + 1, preorder.end());25 //vector<int> inLeft(inorder.begin(), inorder.begin() + pos);26 //vector<int> inRight(inorder.begin() + pos + 1, inorder.end());27 root->val = (*preBegin);28 root->left = build(preBegin + 1, preBegin + pos + 1, inBegin, inBegin + pos);29 root->right = build(preBegin + pos + 1, preEnd, inBegin + pos + 1, inEnd);30 }31 return root;32 }33 TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {34 return build(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());35 }36 };
CE了无数次，RE了好多次是由于边界的问题。
WA是由于使用坐标边界的计算错误。。。
总之就是一个经典题，有很多细节值得深入研究。
2、postorder + inorder
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 public:12 typedef vector<int>::iterator Iter;13 14 TreeNode *build(Iter inBegin, Iter inEnd, Iter postBegin, Iter postEnd) {15 if (inBegin == inEnd || postBegin == postEnd) {16 return NULL;17 }18 Iter target = find(inBegin, inEnd, *(postEnd-1));19 int dis = target - inBegin;20 if (target == inEnd || dis < 0) {21 return NULL;22 }23 TreeNode * root = new TreeNode(*target);24 root->left = build(inBegin, inBegin + dis, postBegin, postBegin + dis);25 root->right = build(inBegin + dis + 1, inEnd, postBegin + dis, postEnd - 1);26 return root;27 }28 TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {29 return build(inorder.begin(), inorder.end(), postorder.begin(), postorder.end());30 }31 };
CE了一次，少写了一个分号，不开心。。。
用迭代器写的思路还是非常清晰的。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。