JZ-004-重建二叉树 java算法-数据结构二叉树

重建二叉树题目描述

【JZ-004-重建二叉树】输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
题目链接: 重建二叉树

代码

import java.util.*; public class Jz04 {// 缓存中序遍历数组每个值对应的索引 private static Map indexForInOrders = new HashMap(); public static TreeNode reConstructBinaryTree(int[] pre, int[] in) { for (int i = 0; i < in.length; i++) { indexForInOrders.put(in[i], i); } return reConstructBinaryTree(pre, 0, pre.length - 1, 0); }/** * 递归 * * @param pre * @param preL * @param preR * @param inL * @return */ private static TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int inL) { if (preL > preR) { return null; } TreeNode root = new TreeNode(pre[preL]); int inIndex = indexForInOrders.get(root.val); int leftTreeSize = inIndex - inL; root.left = reConstructBinaryTree(pre, preL + 1, preL + leftTreeSize, inL); root.right = reConstructBinaryTree(pre, preL + leftTreeSize + 1, preR, inL + leftTreeSize + 1); return root; }public static void main(String[] args) { // 测试用例，并打印最后结果 int[] pre = new int[]{3, 9, 20, 15, 7}; int[] in = new int[]{9, 3, 15, 20, 7}; TreeNode treeNode = reConstructBinaryTree(pre, in); Queue nodes = new LinkedList<>(); nodes.add(treeNode); while (!nodes.isEmpty()) { TreeNode cur = nodes.poll(); if (cur != null) { System.out.println(cur.val + " "); nodes.add(cur.left); nodes.add(cur.right); } } } }