[LeetCode]Construct Binary Tree from Preorder and Inorder 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; 
    } 
    //just make sure (inHigh-inLow == preHigh-preLow), there will be no problem then  
    TreeNode*  BuildTreeInPlusPre(vector<int> &inorder, int inLow, int inHigh, vector<int> &preorder, int preLow, int preHigh ) 
    { 
        if(inLow > inHigh || preLow > preHigh) 
            return NULL; 
        int rootValue = preorder[preLow]; 
        TreeNode* parent = new TreeNode(rootValue); 
        int inRootIdx = m_Value2Index[rootValue]; 
        parent->left = BuildTreeInPlusPre(inorder, inLow, inRootIdx-1, preorder, preLow+1, preLow+inRootIdx-inLow); 
        parent->right = BuildTreeInPlusPre(inorder, inRootIdx+1, inHigh, preorder, preHigh-(inHigh-inRootIdx-1), preHigh); 
        return parent; 
    } 
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) { 
        // Start typing your C/C++ solution below  
        // DO NOT write int main() function  
        BuildMap(inorder); 
        return BuildTreeInPlusPre(inorder, 0, inorder.size()-1, preorder, 0, preorder.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;
 }
 //just make sure (inHigh-inLow == preHigh-preLow), there will be no problem then
 TreeNode*  BuildTreeInPlusPre(vector<int> &inorder, int inLow, int inHigh, vector<int> &preorder, int preLow, int preHigh )
 {
  if(inLow > inHigh || preLow > preHigh)
   return NULL;
  int rootValue = preorder[preLow];
  TreeNode* parent = new TreeNode(rootValue);
  int inRootIdx = m_Value2Index[rootValue];
  parent->left = BuildTreeInPlusPre(inorder, inLow, inRootIdx-1, preorder, preLow+1, preLow+inRootIdx-inLow);
  parent->right = BuildTreeInPlusPre(inorder, inRootIdx+1, inHigh, preorder, preHigh-(inHigh-inRootIdx-1), preHigh);
  return parent;
 }
 TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
  // Start typing your C/C++ solution below
  // DO NOT write int main() function
  BuildMap(inorder);
  return BuildTreeInPlusPre(inorder, 0, inorder.size()-1, preorder, 0, preorder.size()-1);
 }

};

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

上一个：[LeetCode]Construct Binary Tree from Inorder and Postorder Traversal
下一个：[LeetCode]Container With Most Water