LeetCode之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.

preorder:DLR

inorder:  LDR

/**
 * 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 *buildTree(vector<int> &preorder, vector<int> &inorder) {
		return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size()-1);
	 }

	 TreeNode* build(vector<int> & preorder, int  pre_first, int  pre_last,
					 vector<int> & inorder, int  in_first, int  in_last){
		 if (pre_first > pre_last || in_first > in_last)
			 return NULL;
		 TreeNode* root = new TreeNode(preorder[pre_first]);
		 int offset;
		 for (int i = in_first; i <= in_last;i++)
			if (preorder[pre_first] == inorder[i]){
				offset = i - in_first; break;
			}
		root->left = build(preorder, pre_first + 1, pre_first + offset, inorder, in_first, in_first+offset-1);
		root->right = build(preorder, pre_first + offset + 1, pre_last, inorder, in_first+ offset+1,in_last);
	 }
 };

LeetCode之Construct Binary Tree from Preorder and Inorder Traversal,布布扣,bubuko.com

LeetCode之Construct Binary Tree from Preorder and Inorder Traversal

原文：http://blog.csdn.net/smileteo/article/details/22883179