Description

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

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

For example, given

1
2
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

 

Solution

利用先序遍历和中序遍历的特点：先序遍历序列中的第一个节点将中序遍历序列分成左右两个子序列（分别对应左子树和右子树）。

该问题可以递归解决。每次递归需要得到四个序列：

​ 1.左子树的先序遍历序列

​ 2.左子树的中序遍历序列

​ 3.右子树的先序遍历序列

​ 4.右子树的中序遍历序列

这四个序列中，使用1.2.递归继续构造左子树，用3.4.递归构造右子树，当序列中只有1个元素时不再继续构造。

 

Code

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * 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:
    void setOneNode(TreeNode* root, vector<int>& preorder, vector<int>& inorder)
    {
        if(preorder.size() == 0) return;
        root->val = preorder[0];
        root->left = root->right = NULL;
        if(preorder.size() == 1) return;
        vector<int>::iterator pre_it = preorder.begin();
        vector<int>::iterator in_it = inorder.begin();
        for(; *in_it != preorder[0]; in_it++);
        /* 得到左右子树的中序遍历序列 */
        vector<int> inorderLeft(inorder.begin(), in_it);
        in_it++;
        vector<int> inorderRight(in_it, inorder.end());
        pre_it++;
        vector<int> preorderLeft, preorderRight;
        /* 得到左右子树的先序遍历序列 */
        for(int i = 0; i < (int)inorderLeft.size(); i++, pre_it++) preorderLeft.push_back(*pre_it);
        for(int i = 0; i < (int)inorderRight.size(); i++, pre_it++) preorderRight.push_back(*pre_it);
        if(preorderLeft.size())
        {
            root->left = (TreeNode*) malloc(sizeof(TreeNode));
            setOneNode(root->left, preorderLeft, inorderLeft);
        }
        if(preorderRight.size())
        {
            root->right = (TreeNode*) malloc(sizeof(TreeNode));
            setOneNode(root->right, preorderRight, inorderRight);
        }
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
    {
        if(preorder.size() == 0) return NULL;
        TreeNode* root = (TreeNode*) malloc(sizeof(TreeNode));
        setOneNode(root, preorder, inorder);
        return root;
    }
};