[LeetCode]Construct Binary Tree from Inorder and Postorder Traversal-白红宇

[LeetCode]Construct Binary Tree from Inorder and Postorder Traversal

阅读量：4150 次

发布时间：2019-05-25

本文共 2698 字，大约阅读时间需要 8 分钟。

struct TreeNode {	int val;	TreeNode *left;	TreeNode *right;	TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {//Note://You may assume that duplicates do not exist in the tree.//so we can build an unordered_map O(1) to look up the index in inorder, to divide the left subtree and right subtree//in postorder.//inorder{(inStart)left(inRootIdx-1)root(inRootIdx+1)right}, postorder{left(inRootIdx-1)right(PostEnd-1)root}public:	unordered_map
   
     m_Value2Index;//inorder map	void BuildMap(vector
    
      &inorder)	{		m_Value2Index.clear();		for(int i = 0; i < inorder.size(); ++i)			m_Value2Index[inorder[i]] = i;	}	TreeNode*  BuildTreeInPlusPost(vector
     
       &inorder, int inLow, int inHigh, vector
      
        &postorder, int postLow, int postHigh )	{		if(inLow > inHigh || postLow > postHigh)			return NULL;		int rootValue = postorder[postHigh];		TreeNode* parent = new TreeNode(rootValue);		int inRootIdx = m_Value2Index[rootValue];		parent->left = BuildTreeInPlusPost(inorder, inLow, inRootIdx-1, postorder, postLow, postLow+inRootIdx-inLow-1);		parent->right = BuildTreeInPlusPost(inorder, inRootIdx+1, inHigh, postorder, postLow+inRootIdx-inLow, postHigh-1);		return parent;	}    TreeNode *buildTree(vector
       
         &inorder, vector
        
          &postorder) { // Start typing your C/C++ solution below // DO NOT write int main() function BuildMap(inorder); return BuildTreeInPlusPost(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1); } };

second time

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    int findInArray(vector
   
    & array, int s, int e, int target)    {        for(int i = s; i <= e; ++i)            if(array[i] == target) return i;        return -1;    }    TreeNode* buildTreeUtil(vector
    
      & inorder, int is, int ie, vector
     
       & postorder, int ps, int pe)    {        if(ps > pe) return NULL;        int rootVal = postorder[pe];        TreeNode* root = new TreeNode(rootVal);        int idx = findInArray(inorder, is, ie, rootVal);        root->left = buildTreeUtil(inorder, is, idx-1, postorder, ps, idx-1-is+ps);        root->right = buildTreeUtil(inorder, idx+1, ie, postorder, idx-1-is+ps+1, pe-1);        return root;    }    TreeNode *buildTree(vector
      
        &inorder, vector
       
         &postorder) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        return buildTreeUtil(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1);    }};