题目

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

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

大意

给定一颗树的前序和中序序列，重建二叉树。返回根结点。

首先，注意，vector.begin()指向第一个数，end()指向的是最后一个数的后一位。

答案

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
/**
 * 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* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return helper(preorder, preorder.begin(), preorder.end(), inorder, inorder.begin(), inorder.end());
    }
    
    TreeNode* helper(vector<int> pre, vector<int>::iterator begin1, vector<int>::iterator end1,vector<int> in,vector<int>::iterator begin2,vector<int>::iterator end2)
    {
        if(begin1>=end1|| begin2>=end2)  return 0;
        int value = *begin1;
        TreeNode *pNode =new TreeNode(value);
        vector<int>::iterator it = find(begin2, end2, value);  
        int leftlength =it - begin2;
        pNode->left = helper(pre,begin1+1,begin1+1+leftlength,in,begin2,it);
        pNode->right= helper(pre,begin1+1+leftlength,end1,in,it+1,end2);
        return pNode;
    }
};

思路

使用递归，在已知前序和中序时

先序的第一个数一定是根节点，在中序中找相同的数，就可以把中序序列分为两半，然后记录下在中序的指针，计算左边结点的个数，然后使用递归。

106 已知中序和后序，还原二叉树

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
/**
 * 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* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return helper(inorder,inorder.begin(),inorder.end(),postorder,postorder.begin(),postorder.end());
    }
    TreeNode* helper(vector<int> in,vector<int>::iterator begin1,vector<int>::iterator end1,vector<int> post,vector<int>::iterator begin2,vector<int>::iterator end2)
    {
        if(begin1>=end1||begin2>=end2) return 0;
        int value = *(end2-1);
        TreeNode *pnode = new TreeNode(value);
        vector<int>::iterator it = find(begin1,end1,value);
        int leftlength = it-begin1;
        pnode->left = helper(in,begin1,it,post,begin2,begin2+leftlength);
        pnode->right = helper(in,it+1,end1,post,begin2+leftlength,end2-1);
        return pnode;
    }
};