JAVA练习315- 从前序与中序遍历序列构造二叉树

题目概览给定两个整数数组preorder和inorder其中preorder是二叉树的先序遍历inorder是同一棵树的中序遍历请构造二叉树并返回其根节点。示例 1:输入:preorder [3,9,20,15,7], inorder [9,3,15,20,7]输出:[3,9,20,null,null,15,7]示例 2:输入:preorder [-1], inorder [-1]输出:[-1]提示:1 preorder.length 3000inorder.length preorder.length-3000 preorder[i], inorder[i] 3000preorder和inorder均无重复元素inorder均出现在preorderpreorder保证为二叉树的前序遍历序列inorder保证为二叉树的中序遍历序列来源105. 从前序与中序遍历序列构造二叉树 - 力扣LeetCode解题分析方法模拟前序是根 - 左 - 右中序是 左 - 根 - 右。我们可以根据前序数组第一个元素拿到根节点然后再到中序数组中进行拆分我们定义前序数组的范围为 [ pi, pj ]中序数组的范围为 [ ii, ij ]中序数组中根节点的索引为 root那么可以得到每个子数组的范围中序子数组 - 左 [ ii, root - 1 ]中序子数组 - 右 [ root 1, ij ]前序子数组 - 左 [ pi 1, pi root - ii ]前序子数组 - 右 [ pi 1 root - ii, pj ]将这个范围作为参数继续往下传然后重复拿根节点拆分的操作即可直到数组为空或只有一个元素停止。时间复杂度O(n)空间复杂度O(n)/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { int n preorder.length; if (n 0) { return null; } return buildTree(preorder, inorder, 0, n - 1, 0, n - 1); } public TreeNode buildTree(int[] preorder, int[] inorder, int pi, int pj, int ii, int ij) { if (pi pj || ii ij) { return null; } TreeNode node new TreeNode(preorder[pi]); if (pi pj || ii ij) { return node; } int root preorder[pi]; int rootIndex ii; for (int i ii; i ij; i) { if (root inorder[i]) { rootIndex i; } } node.left buildTree(preorder, inorder, pi 1, pi rootIndex - ii, ii, rootIndex - 1); node.right buildTree(preorder, inorder, pi rootIndex - ii 1, pj, rootIndex 1, ij); return node; } }