首页 > 其他 > 详细

leetcode第一刷_Construct Binary Tree from Inorder and Postorder Traversal

时间:2014-05-09 01:23:27      阅读:390      评论:0      收藏:0      [点我收藏+]

这道题是为数不多的感觉在读本科的时候见过的问题。人工构造的过程是怎样呢,后续遍历最后一个节点一定是整棵树的根节点,从中序遍历中查找到这个元素,就可以把树分为两颗子树,这个元素左侧的递归构造左子树,右侧的递归构造右子树,元素本身分配空间,作为根节点。

于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());
    }
};


leetcode第一刷_Construct Binary Tree from Inorder and Postorder Traversal,布布扣,bubuko.com

leetcode第一刷_Construct Binary Tree from Inorder and Postorder Traversal

原文:http://blog.csdn.net/u012792219/article/details/25337991

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!