[LeetCode]Construct Binary Tree from Inorder and Postorder Traversal

[cpp]
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<int, int> m_Value2Index;//inorder map  
    void BuildMap(vector<int> &inorder) 
    { 
        m_Value2Index.clear(); 
        for(int i = 0; i < inorder.size(); ++i) 
            m_Value2Index[inorder[i]] = i; 
    } 
    TreeNode*  BuildTreeInPlusPost(vector<int> &inorder, int inLow, int inHigh, vector<int> &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<int> &inorder, vector<int> &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); 
    } 
     
}; 

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<int, int> m_Value2Index;//inorder map
 void BuildMap(vector<int> &inorder)
 {
  m_Value2Index.clear();
  for(int i = 0; i < inorder.size(); ++i)
   m_Value2Index[inorder[i]] = i;
 }
 TreeNode*  BuildTreeInPlusPost(vector<int> &inorder, int inLow, int inHigh, vector<int> &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<int> &inorder, vector<int> &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);
    }
 
};

补充：软件开发 , C++ ,

上一个：alsa音频架构2--ASoc
下一个：[LeetCode]Construct Binary Tree from Preorder and Inorder Traversal