首页 > 代码库 > leetcode第一刷_Construct Binary Tree from Inorder and Postorder Traversal
leetcode第一刷_Construct Binary Tree from Inorder and Postorder Traversal
这道题是为数不多的感觉在读本科的时候见过的问题。人工构造的过程是怎样呢,后续遍历最后一个节点一定是整棵树的根节点,从中序遍历中查找到这个元素,就可以把树分为两颗子树,这个元素左侧的递归构造左子树,右侧的递归构造右子树,元素本身分配空间,作为根节点。
于set和map容器不同的是,vector容器不含find的成员函数,应该用stl的库函数,好在返回的也是迭代器,而vector的迭代器之间是可以做减法的,偏移量很方便的得到。
TreeNode *buildRec(vector<int> &inorder, int si, vector<int> &postorder, int so, int len){ if(len <= 0) return NULL; TreeNode *root = new TreeNode(postorder[so]); int index = find(inorder.begin(), inorder.end(), postorder[so]) - inorder.begin(); int newlen = index - si; root->left = buildRec(inorder, si, postorder, so-len+newlen, newlen); root->right = buildRec(inorder, index+1, postorder, so-1, len-newlen-1); return root; } class Solution { public: TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) { return buildRec(inorder, 0, postorder, inorder.size()-1, inorder.size()); } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。