依据前序，中序结构二叉树

1. 题目形容

输出某二叉树的前序遍历和中序遍历的后果，请重建出该二叉树。假如输出的前序遍历和中序遍历的后果中都不含反复的数字。

2. 示例

例如，给出

前序遍历 preorder = [3,9,20,15,7] 根， 左， 右

中序遍历 inorder = [9,3,15,20,7] 左， 根， 右

返回如下的二叉树：

3. 解题思路

思路：前序的第一个元素是根结点的值，在中序中找到该值，中序中该值的右边的元素是根结点的左子树，左边是右子树，而后递归的解决右边和左边

具体来说，前序遍历的第一个值肯定为根节点，对应于中序遍历两头的一个点。在中序遍历序列中，这个点左侧的均为根的左子树，这个点右侧的均为根的右子树。这时能够利用递归，别离取前序遍历[1:i+1]和中序遍历的[:i]对应与左子树持续上一个过程，取前序遍历[i+1:]和中序遍历[i+1]对应于右子树持续上一个过程，最终得以重建二叉树。

Python解决会比较简单一些

4. Java实现

/** * Definition for binary tree * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */ import java.util.Arrays; public class Solution {    public TreeNode reConstructBinaryTree(int [] pre,int [] tin) {        if (pre.length == 0 || tin.length == 0){            return null;        }                TreeNode root = new TreeNode(pre[0]);        // 找到 第一个元素在 tin 中的地位        int i = getIndex(tin, pre[0]);                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(tin, 0, i));        root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(tin, i+1, tin.length));                return root;                    }        private int getIndex(int[] array, int value){        int index = 0;        for (int i = 0; i < array.length; i++){            if (array[i] == value){                index = i;                break;            }        }        return index;    }}

5. Python实现

'''输出某二叉树的前序遍历和中序遍历的后果，请重建出该二叉树。假如输出的前序遍历和中序遍历的后果中都不含反复的数字。例如输出前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。''' class TreeNode:    def __init__(self, x):        self.val = x        self.left = None        self.right = Noneclass Solution:    # 返回结构的TreeNode根节点    def reConstructBinaryTree(self, pre, tin):        if not pre or not tin: #只有一个数组为空，则退出函数            return         if set(pre) != set(tin):#如果数组中有反复元素            return                 root = TreeNode(pre[0])        i = tin.index(pre[0])                root.left = self.reConstructBinaryTree(pre[1: i+1], tin[: i])        root.right = self.reConstructBinaryTree(pre[i+1: ], tin[i+1: ])        return root    pre = [1, 2, 3, 5, 6, 4]tin = [5, 3, 6, 2, 4, 1]test = Solution()newTree = test.reConstructBinaryTree(pre, tin)print(newTree)#中序遍历def inorder(newTree):    if newTree:        inorder(newTree.left)        print(newTree.val)        inorder(newTree.right)inorder(newTree)