CodingInterview-重建二叉树

思路是从前序遍历开始，一步一步从中序遍历找到它的左右子树，递归地恢复。

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    vector<int> pre;
    vector<int> vin;
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size()==0 || vin.size()==0 || vin.size()!=pre.size()) return NULL;
        this->pre=pre;
        this->vin=vin;
        TreeNode* root;
        constructor(0,pre.size()-1,0,pre.size()-1,&root);
        return root;
    }
    void constructor(int pLeft,int pRight,int vLeft,int vRight,TreeNode** node){
        if(pLeft>pRight) return;
        bool found=false;
        int vPos=vLeft;
        while(vPos<=vRight){
            if(pre[pLeft]==vin[vPos]){
                found=true;
                break;
            }
            vPos++;
        }
        if(!found) return;
        *node=new TreeNode(pre[pLeft]);
        if(pLeft==pRight) return;
        int leftLength=vPos-vLeft;
        constructor(pLeft+1,pLeft+leftLength,vLeft,vPos-1,&((*node)->left));
        constructor(pLeft+leftLength+1,pRight,vPos+1,vRight,&((*node)->right));
    }
};

一开始的思路是直接使用中序遍历 end 位置来表示前序遍历的 end 位置，但是没想到前序遍历的分割点和中序遍历的分割点不是一样的，这让我调试了很久。其实更关键的是在大脑中预想的时候偷了个懒，没有完全想清楚，感觉差不多就开始写代码，导致后面出现了一系列的错误。