Construct Binary Tree from Inorder and Postorder Traversal (C++ code)

LeetCode Construct Binary Tree from Inorder and Postorder Traversal, Sep 30 '12

难度3，出现频率3

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

思路：  postorder的末位元素是root，在inorder中找root,两边分别是左子树和右子树，递归。

 TreeNode *buildTree(vector<int> &inorder, int istart, int iend, vector<int> &postorder, int pstart, int pend){
    if(istart > iend) return NULL;
    TreeNode *root = new TreeNode(postorder[pend]);  
    int i;
    
    for( i = istart; i <= iend; i++){
      if(inorder[i] == root->val) break;
    }
    if(i > iend) return NULL;
    root->left = buildTree(inorder, istart, i -1, postorder, pstart, pstart + i -1 - istart);
    root->right = buildTree(inorder, i + 1, iend, postorder,  pstart + i - istart , pend - 1);
    return root;
  }

  TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        int  n = postorder.size();
        if(n != inorder.size()) return NULL;
        
      return  buildTree(inorder, 0, n-1, postorder, 0, n-1);
       
       
    } 

LeetCode Construct Binary Tree from Preorder and Inorder TraversalSep 30 '12
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.


思路：同上，preorder的第一个元素是root,在inorder中找root，分开左子树和右子树，递归。

TreeNode *buildTree(vector<int> &preorder, int pstart, int pend, vector<int> &inorder, int istart, int iend){
  if(pstart > pend) return NULL;
  TreeNode *root = new TreeNode(preorder[pstart]);
  int i;
  for(i = istart; i <= iend; i++){
   if(inorder[i] == root->val) break;
  }
 if(i > iend) return NULL;
 int temp = pstart + i - istart;
 root->left = buildTree(preorder, pstart + 1, temp , inorder, istart, i - 1);
 root->right = buildTree(preorder, temp + 1, pend, inorder, i + 1, iend);

 return root;
}

 TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        if(preorder.size() != inorder.size()) return NULL;
        return buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);    
    }