sourcecode

Saturday, November 24, 2012

Construct Binary Tree from Preorder and Inorder Traversal

http://www.leetcode.com/onlinejudge

/**Passed both small and large judge.
Not so many surprise here, just pay extra attention to the boundary indices.
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* build(vector<int> const& preorder, int const pre_first, int const pre_last,
      vector<int> const& inorder, int const in_first, int const in_last){
          if (in_first > in_last) return NULL;
          TreeNode* root = new TreeNode(preorder[pre_first]);
          if (in_first == in_last) return root;
          size_t const r_in = distance(inorder.begin(), 
            find(inorder.begin()+in_first, inorder.begin()+in_last, root->val));
          size_t const sizeLeft = r_in - in_first;//size of left subtree
          root->left = build(preorder, pre_first+1, pre_first+sizeLeft-1,
            inorder, in_first, r_in-1);
          root->right = build(preorder, pre_first+sizeLeft+1, pre_last,
            inorder, r_in+1, in_last);
          return root;
      }
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return build(preorder, 0, preorder.size()-1,
          inorder, 0, inorder.size()-1);
        
    }
};

No comments: