//输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
//
//
//
// 例如，给出
//
// 前序遍历 preorder = [3,9,20,15,7]
//中序遍历 inorder = [9,3,15,20,7]
//
// 返回如下的二叉树：
//
// 3
// / \
// 9 20
// / \
// 15 7
//
//
//
// 限制：
//
// 0 <= 节点个数 <= 5000
//
//
//
// 注意：本题与主站 105 题重复：https://leetcode-cn.com/problems/construct-binary-tree-from-
//preorder-and-inorder-traversal/
// Related Topics 树 递归
// ?? 292 ?? 0
class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder.length <= 0 || inorder.length <= 0) { return null; } return buildTreeCore(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1); } private TreeNode buildTreeCore(int[] preorder, int startPre, int endPre, int[] inorder, int startMid, int endMid) { /*if (startPre > endPre) { return null; }*/ if (startMid > endMid) { return null; } TreeNode root = new TreeNode(preorder[startPre]); // 确定左右子树的长度 int index = findRootIndexInMidTree(inorder, preorder[startPre]); int leftLen = index - startMid; int rightLen = endMid - index; // 前序数组中：startPre + 1是左子树的起点；startPre + leftLen 是左子树的终点 // 中序数组中：index - leftLen 是左子树的起点，index -1 是左子树的终点 root.left = buildTreeCore(preorder, startPre + 1, startPre + leftLen, inorder, index - leftLen, index - 1); // 前序数组中：startPre + 1是左子树的起点；startPre + leftLen 是左子树的终点 // 中序数组中：index - leftLen 是左子树的起点，index -1 是左子树的终点 root.right = buildTreeCore(preorder, endPre - rightLen + 1, endPre, inorder, index + 1, index + rightLen); return root; } private int findRootIndexInMidTree(int[] inorder, int rootVal) { for (int i = 0; i < inorder.length; i++) { if (inorder[i] == rootVal) { return i; } } return -1; } }
原文：https://www.cnblogs.com/noaman/p/14507599.html