秒懂【构建二叉树】！超清晰图解一步步拆解。

1.思路

本题需要通过二叉树的前序遍历结果与中序遍历结果构建出二叉树来，因此需要先了解二叉树前序遍历与中序遍历的规律：

1）前序遍历，根节点是在最前面；

2）中序遍历，根节点是在中间位置（即：根节点元素前面的为左子树，后面的为右子树）。

了解了规律，再来看思路：

alt

根据思路，对应的递推公式如下：

alt

有了递推公式，就可以很方便的写出代码。

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

2.代码

2.1 Python代码

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param preOrder int整型一维数组
# @param vinOrder int整型一维数组
# @return TreeNode类
#
class Solution:
    def reConstructBinaryTree(
        self, pre: List[int], vin: List[int]
    ) -> TreeNode:
        # write code here
        # 2.  递归终止条件（pre、vin长度一样，只需要判断一个即可）
        if len(pre) == 0:
            return None
        # 1. 问题分解（递推公式）
        # 1.1 根节点（前序遍历的第一个值）
        root = TreeNode(pre[0])
        # 1.2 根节点在中序遍历中的位置
        index = self.get_index(vin, pre[0])
        # 1.3 以根节点索引为分割线，将数组pre、vin分为左右两部分
        root.left = self.reConstructBinaryTree(
            pre[1 : index + 1], vin[:index]
        )  # 左部分构成左子树（列表截取：左闭右开）
        root.right = self.reConstructBinaryTree(
            pre[index + 1 :], vin[index + 1 :]
        )  # 右部分构成右子树
        return root

    def get_index(self, vin, data):
        for index in range(len(vin)):
            if vin[index] == data:
                return index  # 根据题目：pre 和 vin 均无重复元素，因此找到元素即可返回
        return 0

2.2 Java代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param preOrder int整型一维数组
     * @param vinOrder int整型一维数组
     * @return TreeNode类
     */
    public TreeNode reConstructBinaryTree (int[] pre, int[] vin) {
        // write code here
        // 2. 递归终止条件（pre、vin长度一样，只需要判断一个即可）
        if (pre.length == 0) {
            return null;
        }

        // 1. 问题分解（递推公式）
        // 1.1 根节点（前序遍历的第一个值）
        TreeNode root = new TreeNode(pre[0]);
        // 1.2 根节点在中序遍历中的位置
        int index = getIndex(vin, pre[0]);
        // 1.3 以根节点索引为分割线，将数组pre、vin分为左右两部分
        root.left = reConstructBinaryTree(
                        Arrays.copyOfRange(pre, 1, index + 1),//数组的截取：左闭右开
                        Arrays.copyOfRange(vin, 0, index));//左部分构成左子树
        root.right = reConstructBinaryTree(
                         Arrays.copyOfRange(pre, index + 1, pre.length),
                         Arrays.copyOfRange(vin, index + 1, vin.length)); //右部分构成右子树

        return root;

    }

    private int getIndex(int[] vin, int data) {
        for (int i = 0; i < vin.length; i++) {
            if (vin[i] == data) {
                return i; //根据题目：pre 和 vin 均无重复元素，因此找到元素即可返回
            }
        }
        return 0;
    }
}

2.3 Go代码

package main

import . "nc_tools"

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param preOrder int整型一维数组
 * @param vinOrder int整型一维数组
 * @return TreeNode类
 */
func reConstructBinaryTree(pre []int, vin []int) *TreeNode {
	// write code here
	// 2. 递归终止条件（pre、vin长度一样，只需要判断一个即可）
	if len(pre) == 0 {
		return nil
	}

	// 1. 问题分解（递推公式）
	// 1.1 根节点（前序遍历的第一个值）
	root := &TreeNode{Val: pre[0]}
	// 1.2 根节点在中序遍历中的位置
	index := getIndex(vin, pre[0])
	// 1.3 以根节点索引为分割线，将数组pre、vin分为左右两部分
	root.Left = reConstructBinaryTree(pre[1:index+1], vin[:index])   //左部分构成左子树（切片截取：左闭右开）
	root.Right = reConstructBinaryTree(pre[index+1:], vin[index+1:]) //右部分构成右子树
	return root
}

func getIndex(vin []int, v int) int {
	for index, data := range vin {
		if data == v {
			return index //根据题目：pre 和 vin 均无重复元素，因此找到元素即可返回
		}
	}
	return 0
}

如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解：B站@好易学数据结构