本文共 1187 字，大约阅读时间需要 3 分钟。

问题描述

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如，给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树：

3   / \  9  20    /  \   15   7

解决思路：

树的相关问题，一般可以考虑使用递归的方法解决，递归树。

class Solution {
       Map
   
     map = new HashMap<>();    int[] preorder;    public TreeNode buildTree(int[] preorder, int[] inorder) {
           //重建二叉树，使用分治的方法        this.preorder = preorder;        //Map缓存        for(int i = 0; i < inorder.length; i++) {
               map.put(inorder[i], i);        }        //回溯 （1）打断条件 （2）逻辑处理 （3）下探  （4）回溯        return trackck(0, 0, preorder.length - 1);    }    public TreeNode trackck(int rootPreIndex, int inorderLeft, int inorderRight) {
           if(inorderLeft > inorderRight) return null;        //获取中序遍历根节点，用于进行左右子树的划分        TreeNode root = new TreeNode(preorder[rootPreIndex]);        int rootInIndex = map.get(preorder[rootPreIndex]);        root.left = trackck(rootPreIndex + 1, inorderLeft, rootInIndex - 1);        root.right = trackck(rootPreIndex + rootInIndex - inorderLeft + 1, rootInIndex + 1, inorderRight);        return root;    }}
   

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/

转载地址：http://wxsu.baihongyu.com/