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;
    }
};