网站开发违约解除合同通知函,WordPress建站布置,做网站公司哪家比较好,网页版qq注册文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目
标题和出处
标题#xff1a;从前序遍历还原二叉树
出处#xff1a;1028. 从前序遍历还原二叉树
难度
6 级
题目描述
要求
我们从二叉树的根结点 root \texttt{root} root 开… 文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目
标题和出处
标题从前序遍历还原二叉树
出处1028. 从前序遍历还原二叉树
难度
6 级
题目描述
要求
我们从二叉树的根结点 root \texttt{root} root 开始深度优先搜索。
在遍历中的每个结点处我们输出 D \texttt{D} D 条短划线其中 D \texttt{D} D 是该结点的深度然后输出该结点的值。如果结点的深度为 D \texttt{D} D则其子结点的深度为 D 1 \texttt{D 1} D 1。根结点的深度为 0 \texttt{0} 0。
如果结点只有一个子结点那么保证该子结点为左子结点。
给出遍历的输出 traversal \texttt{traversal} traversal还原树并返回其根结点 root \texttt{root} root。
示例
示例 1 输入 traversal 1-2--3--4-5--6--7 \texttt{traversal 1-2--3--4-5--6--7} traversal 1-2--3--4-5--6--7 输出 [1,2,5,3,4,6,7] \texttt{[1,2,5,3,4,6,7]} [1,2,5,3,4,6,7]
示例 2 输入 traversal 1-2--3---4-5--6---7 \texttt{traversal 1-2--3---4-5--6---7} traversal 1-2--3---4-5--6---7 输出 [1,2,5,3,null,6,null,4,null,7] \texttt{[1,2,5,3,null,6,null,4,null,7]} [1,2,5,3,null,6,null,4,null,7]
示例 3 输入 traversal 1-401--349---90--88 \texttt{traversal 1-401--349---90--88} traversal 1-401--349---90--88 输出 [1,401,null,349,88,90] \texttt{[1,401,null,349,88,90]} [1,401,null,349,88,90]
数据范围
树中结点数目在范围 [1, 1000] \texttt{[1, 1000]} [1, 1000] 内 1 ≤ Node.val ≤ 10 9 \texttt{1} \le \texttt{Node.val} \le \texttt{10}^\texttt{9} 1≤Node.val≤109
解法
思路和算法
给定的字符串包含每个结点的值和结点所在深度。根结点所在深度为 0 0 0其余结点所在深度都大于 0 0 0。
由于给定的字符串是二叉树的前序遍历序列因此对于遍历到的每个结点如果其层数为 depth \textit{depth} depth depth 0 \textit{depth} 0 depth0其父结点一定是已经遍历的结点中的最后一个访问过的层数为 depth − 1 \textit{depth} - 1 depth−1 的结点。如果父结点的左子结点为空则当前结点作为父结点的左子结点否则当前结点作为父结点的右子结点。
为了定位到最后一个访问过的上一层结点需要使用栈存储结点。栈内结点从栈底到栈顶的深度依次递增根结点位于栈底。
首先从给定的字符串中得到根结点值创建根结点并将根结点入栈。继续遍历字符串的其余部分对于每个结点执行如下操作。 根据短划线数量得到结点所在深度 depth \textit{depth} depth根据短划线后的数值得到结点值 val \textit{val} val使用结点值 val \textit{val} val 创建当前结点。 当前结点的父结点的深度为 depth − 1 \textit{depth} - 1 depth−1。如果栈内元素个数大于 depth \textit{depth} depth则栈顶结点的深度与父结点的深度不同因此将栈顶结点出栈。重复出栈操作直到栈内元素个数等于 depth \textit{depth} depth此时栈顶结点的深度为 depth − 1 \textit{depth} - 1 depth−1。 此时栈顶结点为当前结点的父结点。判断父结点的左子结点是否为空如果父结点的左子结点为空则将当前结点设为父结点的左子结点否则将当前结点设为父结点的右子结点。 将当前结点入栈。
重复上述操作直到字符串遍历结束。遍历结束之后返回根结点即为还原的二叉树。
以下是示例 1 的计算过程。 创建根结点 1 1 1深度为 0 0 0。将结点 1 1 1 入栈 stack [ 1 ] \textit{stack} [1] stack[1]其中左边为栈底右边为栈顶栈内元素为结点此处用数字表示结点且省略父结点和子结点的关系。 创建结点 2 2 2深度为 1 1 1。由于栈内元素个数等于 1 1 1因此将结点 2 2 2 作为栈顶结点 1 1 1 的左子结点将结点 2 2 2 入栈 stack [ 1 , 2 ] \textit{stack} [1, 2] stack[1,2]。 创建结点 3 3 3深度为 2 2 2。由于栈内元素个数等于 2 2 2因此将结点 3 3 3 作为栈顶结点 2 2 2 的左子结点将结点 3 3 3 入栈 stack [ 1 , 2 , 3 ] \textit{stack} [1, 2, 3] stack[1,2,3]。 创建结点 4 4 4深度为 2 2 2。由于栈内元素个数大于 2 2 2因此将结点 3 3 3 出栈此时栈内元素个数等于 2 2 2将结点 4 4 4 作为栈顶结点 2 2 2 的右子结点将结点 4 4 4 入栈 stack [ 1 , 2 , 4 ] \textit{stack} [1, 2, 4] stack[1,2,4]。 创建结点 5 5 5深度为 1 1 1。由于栈内元素个数大于 1 1 1因此将结点 4 4 4 和 2 2 2 出栈此时栈内元素个数等于 1 1 1将结点 5 5 5 作为栈顶结点 1 1 1 的右子结点将结点 5 5 5 入栈 stack [ 1 , 5 ] \textit{stack} [1, 5] stack[1,5]。 创建结点 6 6 6深度为 2 2 2。由于栈内元素个数等于 2 2 2因此将结点 6 6 6 作为栈顶结点 5 5 5 的左子结点将结点 6 6 6 入栈 stack [ 1 , 5 , 6 ] \textit{stack} [1, 5, 6] stack[1,5,6]。 创建结点 7 7 7深度为 2 2 2。由于栈内元素个数大于 2 2 2因此将结点 6 6 6 出栈此时栈内元素个数等于 2 2 2将结点 7 7 7 作为栈顶结点 5 5 5 的右子结点将结点 7 7 7 入栈 stack [ 1 , 5 , 7 ] \textit{stack} [1, 5, 7] stack[1,5,7]。 遍历结束返回根结点 1 1 1。
代码
class Solution {public TreeNode recoverFromPreorder(String traversal) {DequeTreeNode stack new ArrayDequeTreeNode();int rootVal 0;int length traversal.length();int index 0;while (index length Character.isDigit(traversal.charAt(index))) {rootVal rootVal * 10 traversal.charAt(index) - 0;index;}TreeNode root new TreeNode(rootVal);stack.push(root);while (index length) {int depth 0;while (traversal.charAt(index) -) {depth;index;}int val 0;while (index length Character.isDigit(traversal.charAt(index))) {val val * 10 traversal.charAt(index) - 0;index;}TreeNode node new TreeNode(val);while (stack.size() depth) {stack.pop();}TreeNode parent stack.peek();if (parent.left null) {parent.left node;} else {parent.right node;}stack.push(node);}return root;}
}复杂度分析 时间复杂度 O ( m ) O(m) O(m)其中 m m m 是字符串 traversal \textit{traversal} traversal 的长度。需要遍历字符串一次还原二叉树对于二叉树中的每个结点最多入栈和出栈各一次。由于二叉树的结点数 n n n 一定不超过字符串的长度 m m m因此总时间复杂度是 O ( m ) O(m) O(m)。 空间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉树的结点数。空间复杂度主要是栈空间取决于二叉树的高度最坏情况下二叉树的高度是 O ( n ) O(n) O(n)。
