106. Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.
Note:You may assume that duplicates do not exist in the tree.

class Solution {
public:
    TreeNode* createTree(vector<int>& inorder,int in_start,int in_end,vector<int>& postorder,int post_start,int post_end)
    {
        if(in_start>in_end)
           return NULL;
        int root = postorder[post_end];
        int index;
        for(int i=in_start;i<=in_end;i++)
        {
            if(inorder[i] == root)
              index = i;
        }
        int len = index - in_start;
        TreeNode* left = createTree(inorder,in_start,index-1,postorder,post_start,post_start+len-1);
        TreeNode* right = createTree(inorder,index+1,in_end,postorder,post_start+len,post_end-1);
        
        TreeNode* node = new TreeNode(root);
        node->left = left;
        node->right = right;
        return node;
        
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size()==0||postorder.size()==0)
          return NULL;
        return createTree(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1);
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容