题解 | #重建二叉树#

c++

思路

前序遍历的首位肯定是根节点，然后找到它在中序遍历的位置就知道了左子树数组与右子树数组。然后pre里面去与中序的左子树相同的长度就是前序的左子树，二者是对应的，可以敌对进行下一轮计算。
递归内部如果是数组长度0则空节点，如果长度1则叶子节点。二者一定要区分开，产生空节点的原因是因为我们的划分规则

class Solution {
public:
    TreeNode* traversal(vector<int> pre,vector<int> vin){
        if(pre.size()==0) return NULL;
        int rootvalue=pre[0];
        TreeNode* root=new TreeNode(rootvalue);
        if(pre.size()==1) return root;
        int rootindex=0;
        for(;rootindex<vin.size();rootindex++){
            if(vin[rootindex]==rootvalue) break;
        }
        vector<int> leftvin(vin.begin(),vin.begin()+rootindex);
        vector<int> rightvin(vin.begin()+rootindex+1,vin.end());
        vector<int> leftpre(pre.begin()+1,pre.begin()+1+rootindex);
        vector<int> rightpre(pre.begin()+1+rootindex,pre.end());

        root->left=traversal(leftpre,leftvin);
        root->right=traversal(rightpre, rightvin);
        return root;
    }
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size()==0||vin.size()==0) return NULL;
        return traversal(pre,vin);
    }
};