题解 | #重建二叉树#

本题给出了二叉树的前序遍历和中序遍历。

• 前序遍历：根 左 右
• 中序遍历：左 根 右

前序遍历第一个节点为根节点，明确了根节点可以在中序遍历中确定哪些节点为左子树节点，哪些节点为右子树节点。
例如：前序遍历序列{1,2,4,7,3,5,6,8}
中序遍历序列{4,7,2,1,5,3,8,6}
由前序遍历序列可知，1 为二叉树的根节点，根据中序遍历可知，4，7，2为左子树节点，5，3，8，6为右子树节点。然后再递归构建左子树和右子树。
代码如下：

class Solution {
public:
    TreeNode* rebuild(vector<int>& pre,int pre_left,int pre_right, vector<int>& vin,int vin_left,int vin_right){
        if(pre_left > pre_right || vin_left>vin_right) return nullptr;

        TreeNode *root = new TreeNode(pre[pre_left]);
        for(int i=vin_left; i<=vin_right; i++){
            if(root->val==vin[i]){
                root->left = rebuild(pre,pre_left+1,i-vin_left+pre_left,vin,vin_left,i-1);
                root->right = rebuild(pre,pre_left+i-vin_left+1,pre_right,vin,i+1,vin_right);
                break;
            }
        }
        return root;
    }
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        return rebuild(pre,0,pre.size()-1,vin,0,vin.size()-1);
    }
};