重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

1.前序遍历的的第一个元素是根节点。

2.中序遍历中根节点的左边的节点构成左子树，右边构成右子树。

根据以上两条性质，我们可以先重建二叉树的根节点，构建完根节点后我们就可以将问题拆分成其左右两子树的二叉树重建问题。

根据解法我们最容易想到的解法就是递归。

/**
 * 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) {
        if(!preorder.size())
            return NULL;
        TreeNode*  root = new TreeNode(preorder[0]);
        
        vector<int>  preLeft, preRight, inLeft, inRight;
        bool t = 1;
        for(int i = 0; i < inorder.size(); i++){
            if(inorder[i] == root->val){
                t = 0;
                continue;
            }
            if(t){
                inLeft.push_back(inorder[i]);
            }
            else{
                inRight.push_back(inorder[i]);
            }
        }
        for(int i = 0; i < inLeft.size(); i++)
            preLeft.push_back(preorder[i+1]);
        for(int i = 0; i < inRight.size(); i++)
            preRight.push_back(preorder[i+1+preLeft.size()]);
        
            root->left = buildTree(preLeft, inLeft);
        
            root->right = buildTree(preRight, inRight);
        return  root;
    }
};

通过测试结果，递归方法无论是在时间复杂度还是空间复杂度都是很大的。而且随着递归的层次越来越深，程序有溢出栈的风险。

解决空间复杂度：

在递归方法中，多次定义了vector类型的变量来存放前序遍历结果和中序遍历结果，这增大了对内存的消耗，为了解决这个问题，我们最朴素的办法就是使用两个双指针对最初的前序结果和中序结果重复利用。

/**
 * 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:
    vector<int> preorde;
    vector<int> inorde;
    void  test(TreeNode *&root, int preLeft, int preRight, int inLeft, int inRight){
        if(preLeft > preRight)
            return ;
        
        root = new TreeNode(preorde[preLeft]);
        int index = inLeft-1;
        while(inorde[++index] != root->val);
?
        test(root->left, preLeft+1, index-inLeft+preLeft, inLeft, index-1);
        test(root->right, index-inLeft+preLeft+1 , preRight, index+1, inRight);
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(!preorder.size())
            return NULL;
        TreeNode*  root = new TreeNode(preorder[0]);
        preorde = preorder;
        inorde = inorder;
        int index = -1;
        while(inorder[++index] != preorder[0]);
?
        test(root->left, 1, index,  0, index-1);
        test(root->right,(index)+1, preorder.size()-1, index+1, inorder.size()-1);
        return  root;
    }
};

重建二叉树

原文：https://www.cnblogs.com/hxj568/p/14613309.html