LeetCode Q105: Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Solution:

Basic binary tree question, but need to take care of boundary of array index.

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	TreeNode* helper(vector<int>& preorder, long pre_start, long pre_end,
	vector<int>& inorder, long in_start, long in_end)
	{
	if(pre_start>pre_end || pre_start>=preorder.size() || pre_end<0){
	return NULL;
	}
	TreeNode* newNode=new TreeNode(preorder[pre_start]);
	//find
	long pos=in_start;
	while(inorder[pos]!=preorder[pre_start]){pos++;}
	long l_in_start=in_start;
	long l_in_end=pos-1;
	long r_in_start=pos+1;
	long r_in_end=in_end;
	long l_num=max(long(0), l_in_end-l_in_start+1);
	long r_num=max(long(0), r_in_end-r_in_start+1);
	long l_pre_start=l_num==0? INT_MAX:pre_start+1;
	long l_pre_end=l_pre_start+l_num-1;
	long r_pre_start=l_num==0? pre_start+1:l_pre_end+1;
	r_pre_start=r_pre_start>pre_end? INT_MAX:r_pre_start;
	long r_pre_end=r_pre_start+r_num-1;
	TreeNode* lnode=helper(preorder, l_pre_start, l_pre_end,
	inorder, l_in_start, l_in_end);
	TreeNode* rnode=helper(preorder, r_pre_start, r_pre_end,
	inorder, r_in_start, r_in_end);
	newNode->left=lnode;
	newNode->right=rnode;
	return newNode;
	}
	TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
	TreeNode* root=helper(preorder, 0, preorder.size()-1,
	inorder, 0, inorder.size()-1);
	return root;
	}
	};

view raw Q105.cpp hosted with ❤ by GitHub

Round2 solution:
Following solution is shorter, though result in a Memory Limit Exceeded.

	class Solution {
	public:
	TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
	if(preorder.empty()){
	return NULL;
	}
	vector<int> pre_left;
	vector<int> pre_right;
	vector<int> in_left;
	vector<int> in_right;
	int j=-1;
	for(int i=0; i<inorder.size(); i++){
	if(inorder[i]==preorder[0]) {j=i; continue;}
	if(j==-1)
	in_left.push_back(inorder[i]);
	else
	in_right.push_back(inorder[i]);
	}
	for(int i=1; i<preorder.size(); i++){
	if(i<=j)
	pre_left.push_back(preorder[i]);
	else
	pre_right.push_back(preorder[i]);
	}
	TreeNode* node = new TreeNode (preorder[0]);
	TreeNode* node_left = buildTree(pre_left, in_left);
	TreeNode* node_right = buildTree(pre_right, in_right);
	node->left = node_left;
	node->right = node_right;
	return node;
	}
	};

view raw Q105Rnd2.cpp hosted with ❤ by GitHub