LeetCode/105.cpp at master · guihunkun/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 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* helperPreIn(vector<int>& preorder, vector<int>& inorder, int prestart, int preend, int instart, int inend)
	{
		if(prestart > preend || instart > inend) {
			return NULL;
		}

		TreeNode* node =new TreeNode(preorder[prestart]);
		int i;
		for(i = instart; i <= inend; i++)
		{
			if(inorder[i] == node->val) {
				break;
			}
		}

		node->left=helperPreIn(preorder, inorder, prestart + 1, prestart + i - instart, instart, i - 1);
		node->right=helperPreIn(preorder , inorder, prestart + i - instart + 1, preend, i + 1, inend);
		return node;
	}

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