设计网站需要什么条件,郑州网站建设e橙网,开发者模式有什么危害,东莞最好的网站建设价格文章目录 题目标题和出处难度题目描述要求示例数据范围 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目
标题和出处
标题#xff1a;从前序与中序遍历序列构造二叉树
出处#xff1a;105. 从前序与中序遍历序列构造二叉树
难度
5 级
题目描述
要… 文章目录 题目标题和出处难度题目描述要求示例数据范围 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目
标题和出处
标题从前序与中序遍历序列构造二叉树
出处105. 从前序与中序遍历序列构造二叉树
难度
5 级
题目描述
要求
给定两个整数数组 preorder \texttt{preorder} preorder 和 inorder \texttt{inorder} inorder其中 preorder \texttt{preorder} preorder 是二叉树的前序遍历 inorder \texttt{inorder} inorder 是同一个树的中序遍历请构造并返回二叉树。
示例
示例 1 输入 preorder [3,9,20,15,7], inorder [9,3,15,20,7] \texttt{preorder [3,9,20,15,7], inorder [9,3,15,20,7]} preorder [3,9,20,15,7], inorder [9,3,15,20,7] 输出 [3,9,20,null,null,15,7] \texttt{[3,9,20,null,null,15,7]} [3,9,20,null,null,15,7]
示例 2
输入 preorder [-1], inorder [-1] \texttt{preorder [-1], inorder [-1]} preorder [-1], inorder [-1] 输出 [-1] \texttt{[-1]} [-1]
数据范围 1 ≤ preorder.length ≤ 3000 \texttt{1} \le \texttt{preorder.length} \le \texttt{3000} 1≤preorder.length≤3000 inorder.length preorder.length \texttt{inorder.length} \texttt{preorder.length} inorder.lengthpreorder.length -3000 ≤ preorder[i], inorder[i] ≤ 3000 \texttt{-3000} \le \texttt{preorder[i], inorder[i]} \le \texttt{3000} -3000≤preorder[i], inorder[i]≤3000 preorder \texttt{preorder} preorder 和 inorder \texttt{inorder} inorder 都由不同的值组成 inorder \texttt{inorder} inorder 中的每个值均出现在 preorder \texttt{preorder} preorder 中 preorder \texttt{preorder} preorder 保证为二叉树的前序遍历序列 inorder \texttt{inorder} inorder 保证为二叉树的中序遍历序列
解法一
思路和算法
由于二叉树中的每个结点值各不相同因此可以根据结点值唯一地确定结点。
二叉树的前序遍历的方法为依次遍历根结点、左子树和右子树对于左子树和右子树使用同样的方法遍历。
二叉树的中序遍历的方法为依次遍历左子树、根结点和右子树对于左子树和右子树使用同样的方法遍历。
前序遍历序列的第一个元素值为根结点值只要在中序遍历序列中定位到根结点值的下标即可得到左子树中的结点数和右子树中的结点数。对于左子树和右子树也可以在给定的前序遍历序列和中序遍历序列中分别得到对应的子序列根据子序列构造相应的子树。当子树构造完毕时原始二叉树即可构造完毕。
上述构造二叉树的过程是一个递归分治的过程。将二叉树分成根结点、左子树和右子树三部分首先构造左子树和右子树然后构造原始二叉树构造左子树和右子树是原始问题的子问题。
分治的终止条件是子序列为空此时构造的子树为空。当子序列不为空时首先得到根结点值以及左子树和右子树对应的子序列然后递归地构造左子树和右子树。
实现方面有两点需要注意。 在中序遍历序列中定位根结点值的下标时简单的做法是遍历整个序列寻找根结点值该做法的时间复杂度较高。可以使用哈希表存储每个结点值在中序遍历序列中的下标即可在 O ( 1 ) O(1) O(1) 的时间内定位到任意结点值在中序遍历序列中的下标。 对于左子树和右子树的构造需要使用子序列此处的子序列实质为下标连续的子数组。为了降低时间复杂度和空间复杂度使用开始下标和子数组长度确定子数组则不用新建数组和复制数组元素而且可以复用哈希表存储的每个结点值在中序遍历序列中的下标信息。
代码
class Solution {MapInteger, Integer inorderIndices new HashMapInteger, Integer();int[] preorder;int[] inorder;public TreeNode buildTree(int[] preorder, int[] inorder) {this.preorder preorder;this.inorder inorder;int length preorder.length;for (int i 0; i length; i) {inorderIndices.put(inorder[i], i);}return buildTree(0, 0, length);}public TreeNode buildTree(int preorderStart, int inorderStart, int nodesCount) {if (nodesCount 0) {return null;}int rootVal preorder[preorderStart];TreeNode root new TreeNode(rootVal);int inorderRootIndex inorderIndices.get(rootVal);int leftNodesCount inorderRootIndex - inorderStart;int rightNodesCount nodesCount - 1 - leftNodesCount;root.left buildTree(preorderStart 1, inorderStart, leftNodesCount);root.right buildTree(preorderStart 1 leftNodesCount, inorderRootIndex 1, rightNodesCount);return root;}
}复杂度分析 时间复杂度 O ( n ) O(n) O(n)其中 n n n 是数组 preorder \textit{preorder} preorder 和 inorder \textit{inorder} inorder 的长度即二叉树的结点数。将中序遍历序列中的每个结点值与下标的对应关系存入哈希表需要 O ( n ) O(n) O(n) 的时间构造二叉树也需要 O ( n ) O(n) O(n) 的时间。 空间复杂度 O ( n ) O(n) O(n)其中 n n n 是数组 preorder \textit{preorder} preorder 和 inorder \textit{inorder} inorder 的长度即二叉树的结点数。空间复杂度主要是递归调用的栈空间以及哈希表空间因此空间复杂度是 O ( n ) O(n) O(n)。
解法二
思路和算法
使用迭代的方法构造二叉树需要充分利用二叉树遍历的性质考虑遍历序列中相邻结点的关系。
对于前序遍历序列中的两个相邻的值 x x x 和 y y y其对应结点的关系一定是以下两种情况之一 结点 y y y 是结点 x x x 的左子结点 结点 x x x 没有左子结点结点 y y y 是结点 x x x 的右子结点或者结点 y y y 是结点 x x x 的某个祖先结点的右子结点。
对于第 1 种情况在中序遍历序列中 y y y 在 x x x 前面且 y y y 和 x x x 相邻。对于第 2 种情况在中序遍历序列中 x x x 在 y y y 前面。
判断前序遍历序列中的两个相邻的值属于哪一种情况需要借助中序遍历序列。由于中序遍历访问右子树在访问根结点之后因此可以比较前序遍历序列的上一个结点值和中序遍历序列的当前结点值判断属于哪一种情况 如果前序遍历序列的上一个结点值和中序遍历序列的当前结点值不同则前序遍历序列的上一个结点有左子结点属于第 1 种情况 如果前序遍历序列的上一个结点值和中序遍历序列的当前结点值相同则前序遍历序列的上一个结点没有左子结点属于第 2 种情况。
注意在第 1 种情况下中序遍历序列的结点值顺序恰好和前序遍历序列的结点值顺序相反可以使用栈实现反转序列。
具体做法是遍历前序遍历序列对于每个值分别创建结点将每个结点作为上一个结点的左子结点并将每个结点入栈直到前序遍历序列的上一个结点值等于中序遍历序列的当前结点值。然后遍历中序遍历序列并依次将栈内的结点出栈直到栈顶结点值和中序遍历序列的当前结点值不同此时前序遍历序列的当前值对应的结点为最后一个出栈的结点的右子结点将当前结点入栈。然后对前序遍历序列和中序遍历序列的其余值继续执行上述操作直到遍历结束时二叉树构造完毕。
以下用一个例子说明构造二叉树的过程。已知二叉树的前序遍历序列是 [ 1 , 10 , 8 , 9 , 5 , 7 , 15 , 12 , 20 , 13 ] [1, 10, 8, 9, 5, 7, 15, 12, 20, 13] [1,10,8,9,5,7,15,12,20,13]中序遍历序列是 [ 9 , 5 , 8 , 10 , 7 , 1 , 12 , 15 , 13 , 20 ] [9, 5, 8, 10, 7, 1, 12, 15, 13, 20] [9,5,8,10,7,1,12,15,13,20]二叉树如图所示。 初始时中序遍历序列的下标是 0 0 0。以下将中序遍历序列的下标处的值称为中序遍历序列的当前结点值。 将前序遍历序列的下标 0 0 0 的元素 1 1 1 作为根结点值创建根结点并将根结点入栈。 当遍历到前序遍历序列的 10 10 10 时上一个结点值和中序遍历序列的当前结点值不同因此创建结点 10 10 10作为结点 1 1 1 的左子结点并将结点 10 10 10 入栈。 当遍历到前序遍历序列的 8 8 8 时上一个结点值和中序遍历序列的当前结点值不同因此创建结点 8 8 8作为结点 10 10 10 的左子结点并将结点 8 8 8 入栈。 当遍历到前序遍历序列的 9 9 9 时上一个结点值和中序遍历序列的当前结点值不同因此创建结点 9 9 9作为结点 8 8 8 的左子结点并将结点 9 9 9 入栈。 当遍历到前序遍历序列的 5 5 5 时上一个结点值是 9 9 9和中序遍历序列的当前结点值相同因此遍历中序遍历序列并将栈内的结点 9 9 9 出栈此时中序遍历序列的下标移动到 1 1 1。创建结点 5 5 5将结点 5 5 5 作为结点 9 9 9 的右子结点并将结点 5 5 5 入栈。 当遍历到前序遍历序列的 7 7 7 时上一个结点值是 5 5 5和中序遍历序列的当前结点值相同因此遍历中序遍历序列并将栈内的结点 5 5 5、 8 8 8、 10 10 10 出栈此时中序遍历序列的下标移动到 4 4 4。创建结点 7 7 7将结点 7 7 7 作为结点 10 10 10 的右子结点并将结点 7 7 7 入栈。 当遍历到前序遍历序列的 15 15 15 时上一个结点值是 7 7 7和中序遍历序列的当前结点值相同因此遍历中序遍历序列并将栈内的结点 7 7 7、 1 1 1 出栈此时中序遍历序列的下标移动到 6 6 6。创建结点 15 15 15将结点 15 15 15 作为结点 1 1 1 的右子结点并将结点 15 15 15 入栈。 当遍历到前序遍历序列的 12 12 12 时上一个结点值和中序遍历序列的当前结点值不同因此创建结点 12 12 12作为结点 15 15 15 的左子结点并将结点 12 12 12 入栈。 当遍历到前序遍历序列的 20 20 20 时上一个结点值是 12 12 12和中序遍历序列的当前结点值相同因此遍历中序遍历序列并将栈内的结点 12 12 12、 15 15 15 出栈此时中序遍历序列的下标移动到 8 8 8。创建结点 20 20 20将结点 20 20 20 作为结点 15 15 15 的右子结点并将结点 20 20 20 入栈。 当遍历到前序遍历序列的 13 13 13 时上一个结点值和中序遍历序列的当前结点值不同因此创建结点 13 13 13作为结点 20 20 20 的左子结点并将结点 13 13 13 入栈。
此时遍历结束二叉树构造完毕。
代码
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {int length preorder.length;TreeNode root new TreeNode(preorder[0]);DequeTreeNode stack new ArrayDequeTreeNode();stack.push(root);int inorderIndex 0;for (int i 1; i length; i) {TreeNode prev stack.peek();TreeNode curr new TreeNode(preorder[i]);if (prev.val ! inorder[inorderIndex]) {prev.left curr;} else {while (!stack.isEmpty() stack.peek().val inorder[inorderIndex]) {prev stack.pop();inorderIndex;}prev.right curr;}stack.push(curr);}return root;}
}复杂度分析 时间复杂度 O ( n ) O(n) O(n)其中 n n n 是数组 preorder \textit{preorder} preorder 和 inorder \textit{inorder} inorder 的长度即二叉树的结点数。前序遍历序列和中序遍历序列各需要遍历一次构造二叉树需要 O ( n ) O(n) O(n) 的时间。 空间复杂度 O ( n ) O(n) O(n)其中 n n n 是数组 preorder \textit{preorder} preorder 和 inorder \textit{inorder} inorder 的长度即二叉树的结点数。空间复杂度主要是栈空间取决于二叉树的高度最坏情况下二叉树的高度是 O ( n ) O(n) O(n)。
