wordpress产品网站,建设网站建设什么挣钱,东莞太子酒店,怎样做站长建网站106. 从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder #xff0c;其中 inorder 是二叉树的中序遍历#xff0c; postorder 是同一棵树的后序遍历#xff0c;请你构造并返回这颗 二叉树 。
示例 1: 输入#xff1a; inorder [9,3,15,20,7], post…106. 从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。
示例 1: 输入 inorder [9,3,15,20,7], postorder [9,15,7,20,3] 输出[3,9,20,null,null,15,7]
示例 2:
输入 inorder [-1], postorder [-1] 输出[-1]
提示: 1 ≤ i n o r d e r . l e n g t h ≤ 3000 1 \leq inorder.length \leq 3000 1≤inorder.length≤3000postorder.length inorder.length − 3000 ≤ i n o r d e r [ i ] , p o s t o r d e r [ i ] ≤ 3000 -3000 \leq inorder[i], postorder[i] \leq 3000 −3000≤inorder[i],postorder[i]≤3000inorder 和 postorder 都由 不同 的值组成postorder 中每一个值都在 inorder 中inorder 保证是树的中序遍历postorder 保证是树的后序遍历
解法一(递归分治Map哈希)
思路分析
对于该题首先思考中序遍历为左中右后序遍历为左右中因此通过后序遍历可以确认二叉树的根节点然后通过根节点可以对中序遍历进行切割成左中序、右中序然后根据得到的左中序长度可以对后序遍历进行切割成左后序、右后序以此类推通过递归分治的方式可以从根节点建立一个二叉树。同时思考递归的参数和返回值因为题目要求构造一个二叉树所以 返回值类型为TreeNode然后对于递归的参数则包括中序遍历数组、后序遍历数组、中序数组起始位置、中序数组末尾位置、后序数组起始位置、后序数组末尾位置。对于递归的边界条件则当后序遍历数组为null时返回null当由后序遍历索引起始及末尾位置得数组长度为1时直接返回对于递归的过程则是构造中间节点以及递归构造左右节点同时对于如何根据后序数组对中序数组进行分割可以使用Map哈希表的方式避免对中序数组进行反复查询。
实现代码如下
class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {if (postorder null)return null; // 边界条件// 构造哈希表MapInteger, Integer inMap new HashMap();for (int i 0; i inorder.length; i) {inMap.put(inorder[i], i);}return doBuildTree(inorder, postorder, inMap, 0, inorder.length-1, 0, postorder.length-1);}private TreeNode doBuildTree(int[] inorder, int[] postorder, MapInteger, Integer inMap, int inS, int inE, int postS, int postE) {if (inE 0 || postE 0 || inS inE || postS postE || inS inorder.length || postS postorder.length) // 考虑边界问题return null;// 根据后序遍历数组 末尾索引 获取该子树根节点值int rootValue postorder[postE];TreeNode node new TreeNode(rootValue); // 构造二叉树if (postS postE) // 若此时后序数组 起始索引和末尾索引相等 说明为叶子节点return node; // 直接返回// 根据根节点值 对中序数组进行分割 获取分割位置索引int index inMap.get(rootValue);// 递归获取左右子树node.left doBuildTree(inorder, postorder, inMap, inS, index-1, postS, postSindex-1-inS);node.right doBuildTree(inorder, postorder, inMap, index1, inE, postSindex-inS, postE-1);return node;}
}提交结果如下 解答成功: 执行耗时:2 ms,击败了62.35% 的Java用户 内存消耗:43.5 MB,击败了13.55% 的Java用户 复杂度分析
时间复杂度 O ( n m ) O(nm) O(nm)需要遍历数组空间复杂度 O ( n m ) O(nm) O(nm)考虑递归对空间的消耗
优化解法一
思路分析
通过对解法一代码的执行流程发现递归函数doBuildTree中的inorder参数可以省略且对于doBuildTree函数中的边界问题判断由于初始inE与PostE均为len-1inS与postS初始为0因此对于inE 0的判断与inS inorder.length的判断包含在inS inE中可省略
实现代码如下
class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {if (postorder null)return null; // 边界条件// 构造哈希表MapInteger, Integer inMap new HashMap();for (int i 0; i inorder.length; i) {inMap.put(inorder[i], i);}return doBuildTree(postorder, inMap, 0, inorder.length-1, 0, postorder.length-1);}private TreeNode doBuildTree(int[] postorder, MapInteger, Integer inMap, int inS, int inE, int postS, int postE) {if (inS inE || postS postE) // 考虑边界问题return null;// 根据后序遍历数组 末尾索引 获取该子树根节点值int rootValue postorder[postE];TreeNode node new TreeNode(rootValue); // 构造二叉树if (postS postE) // 若此时后序数组 起始索引和末尾索引相等 说明为叶子节点return node; // 直接返回// 根据根节点值 对中序数组进行分割 获取分割位置索引int index inMap.get(rootValue);// 递归获取左右子树node.left doBuildTree(postorder, inMap, inS, index-1, postS, postSindex-1-inS);node.right doBuildTree(postorder, inMap, index1, inE, postSindex-inS, postE-1);return node;}
}提交结果如下 解答成功: 执行耗时:2 ms,击败了62.35% 的Java用户 内存消耗:43.6 MB,击败了10.93% 的Java用户 复杂度分析
时间复杂度 O ( n m ) O(nm) O(nm)遍历中序数组和后序数组空间复杂度 O ( n m ) O(nm) O(nm)考虑每层递归传递参数对空间消耗。
解法二(递归分治Map)
思路分析
跟据官方题解将中序数组、后序数组以及提交查询的Map变量均改为全局遍历即不需要作为递归函数参数可在递归函数内访问。因为后序遍历中最后一个元素为子树的根节点所以先递归获取右子树再递归获取左子树
实现代码如下
class Solution {int[] inorder; // 中序遍历数组int[] postorder; // 后序遍历数组MapInteger, Integer inMap; // 中序遍历数组 索引表int postIndex;public TreeNode buildTree(int[] inorder, int[] postorder) {if (postorder null)return null; // 边界条件this.inorder inorder;this.postorder postorder;postIndex postorder.length-1;// 构造哈希表inMap new HashMap();for (int i 0; i inorder.length; i) {inMap.put(inorder[i], i);}return doBuildTree(0, inorder.length-1);}private TreeNode doBuildTree(int inLeft, int inRight) {if (inLeft inRight) // 说明此时为空树return null;int value postorder[postIndex]; // 根据postIndex 来确定当前子树 中节点值TreeNode node new TreeNode(value);// 根据 中间节点值 获取分割中序数组索引int index inMap.get(value);postIndex--; // 移动所指向的根节点// 先获取右子树node.right doBuildTree(index1, inRight);// 再获取左子树node.left doBuildTree(inLeft, index-1);return node;}
}提交结果如下 解答成功: 执行耗时:1 ms,击败了99.58% 的Java用户 内存消耗:43.2 MB,击败了32.11% 的Java用户 复杂度分析
时间复杂度 O ( n ) O(n) O(n)n表示树的节点个数空间复杂度 O ( n ) O(n) O(n)需要使用 O ( n ) O(n) O(n)的空间存储哈希表同时 O ( h ) O(h) O(h)的空间进行递归(即二叉树的高度)且h n
