105.从前序与中序遍历序列构造二叉树

package org.example; import java.util.HashMap; import java.util.Map; class Solution { /** * 缓存 key结点的值 value该结点值在中序遍历结果数组中的索引 */ private final MapInteger, Integer cache new HashMap(); public TreeNode buildTree(int[] preorder, int[] inorder) { // 构建缓存 for (int i 0; i inorder.length; i) { cache.put(inorder[i], i); } // 还原二叉树并返回二叉树的根结点 return buildTree(preorder, // 二叉树的前序遍历结果 0, // 该二叉树前序遍历结果的起始位置 preorder.length - 1, // 该二叉树前序遍历结果的结束位置 inorder, // 二叉树的中序遍历结果 0, // 该二叉树中序遍历结果的起始位置 inorder.length - 1 // 该二叉树中序遍历结果的结束位置 ); } /** * 根据二叉树的前序遍历结果和中序遍历结果来还原二叉树 * * param preorder 二叉树的前序遍历结果 * param preorderLeft 该二叉树前序遍历结果的起始位置 * param preorderRight 该二叉树前序遍历结果的结束位置 * param inorder 二叉树的中序遍历结果 * param inorderLeft 该二叉树中序遍历结果的起始位置 * param inorderRight 该二叉树中序遍历结果的结束位置 * return 还原得到的二叉树 */ private TreeNode buildTree(int[] preorder, // 二叉树的前序遍历结果 int preorderLeft, // 该二叉树前序遍历结果的起始位置 int preorderRight, // 该二叉树前序遍历结果的结束位置 int[] inorder, // 二叉树的中序遍历结果 int inorderLeft, // 该二叉树中序遍历结果的起始位置 int inorderRight // 该二叉树中序遍历结果的结束位置 ) { if (preorderLeft preorderRight) { return null; } // 二叉树的根结点的值 int rootValue preorder[preorderLeft]; // 在中序遍历结果数组中定位该值的索引 int rootIndex cache.get(rootValue); // 计算该二叉树的左子树的结点的数量 int leftCount rootIndex - inorderLeft; // 构建根结点 TreeNode root new TreeNode(rootValue); // 递归地构建根结点的左子树 root.left buildTree(preorder, // 二叉树的前序遍历结果 preorderLeft 1, // 左子树前序遍历结果的起始位置 preorderLeft leftCount, // 左子树前序遍历结果的结束位置 inorder, // 二叉树的中序遍历结果 inorderLeft, // 左子树中序遍历结果的起始位置 rootIndex - 1 // 左子树中序遍历结果的结束位置 ); // 递归地构建根结点的右子树 root.right buildTree(preorder, // 二叉树的前序遍历结果 preorderLeft leftCount 1, // 右子树前序遍历结果的起始位置 preorderRight, // 右子树前序遍历结果的结束位置 inorder, // 二叉树的中序遍历结果 rootIndex 1, // 右子树中序遍历结果的起始位置 inorderRight // 右子树中序遍历结果的结束位置 ); // 返回根结点 return root; } }