JZ4 重建二叉樹 （二叉樹的前序，中序和後序周遊）

JZ4 重建二叉樹

• 題目描述
• 思路分析
• 代碼實作

題目描述

點這裡

思路分析

二叉樹的周遊相關

首先要熟悉三種周遊：前序周遊（中左右），中序周遊（左中右）和後序周遊（左右中）

例如輸入前序周遊序列{1,2,4,7,3,5,6,8}和中序周遊序列{4,7,2,1,5,3,8,6}，每次先從前序周遊的開頭找到1。再在中序周遊中找到1的位置記作k（位置為3，所有k=3），k前邊有3個數（4，7，2），後邊有四個數（5，3，8，6），是以在前序周遊中1後邊連續的3個數是左子樹（左子樹區間确定），再往後的4個數為右子樹（右子樹區間也确定）。遞歸處理左子樹和右子樹即可。

代碼實作

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorder,inorder;
    unordered_map<int,int> hash;
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        preorder=pre,inorder=vin;
        for(int i=0;i<vin.size();i++) hash[vin[i]]=i;
        return dfs(0,preorder.size()-1,0,inorder.size()-1);
    }
    TreeNode* dfs(int pl,int pr,int il,int ir){
        if(pl>pr) return NULL;
        auto root=new TreeNode(preorder[pl]);
        int k=hash[root->val];
        auto left=dfs(pl+1,pl+k-il,il,k-1);
        auto right=dfs(pl+k-il+1,pr,k+1,ir);
        root->left=left,root->right=right;
        return root;
    }
};