1028。RecoveringabinarytreefrompreordertraversalPreorder-traversaltopic我们从二叉树的根节点root开始进行深度优先搜索。在遍历中的每个节点，我们输出D个破折号（其中D是节点的深度），然后是节点的值。（如果一个节点的深度为D，则其直接子节点的深度为D+1。根节点的深度为0）。如果节点只有一个孩子，那么这个孩子肯定是左孩子。给定遍历输出S，恢复树并返回其根节点root。示例1：输入：“1-2--3--4-5--6--7”输出：[1,2,5,3,4,6,7]示例2：输入：“1-2--3---4-5--6---7"输出：[1,2,5,3,null,6,null,4,null,7]示例3：输入："1-401--349---90--88"输出：[1,401,null,349,88,90]提示：原树的节点数在1到1000之间，每个节点的值在1到10^9之间.解题思路：堆栈+迭代根据题意，结合例子和图例，可以得到如下信息：遍历一个字符串时，读-个字符，直到遇到一个非-字符。此时，我们可以通过-的个数来判断当前节点的深度。（也印证了题目中所说的[Ateachnodeinthetraversal,weoutputDdashes(whereDisthedepthofthenode)]）；读取数字（这里注意示例3，数字不仅是单个数字），直到遇到非数字。这些数字就是节点的值。题目中提到【如果节点只有一个子节点，则保证该子节点为左子节点。】，根据这个前提开始分析。假设当前节点是A，前一个节点是B，那么这里可能有两种情况：A是B的左子节点；A不是B的左子节点；第一种情况就不解释了，这相当于考虑前面的前提，因为当一个节点只有一个子节点时，这个节点优先作为左子节点。所以这里先建左子树。因为本文使用栈来帮助解决问题，栈中存放的是等待构建子树的节点，构建子树时弹出栈。如果当前节点的深度<栈的大小，这说明前一个节点不是当前节点的左子节点，属于第二种情况，（根据前面讲的题目，如果节点只有一个子节点，这个子节点就是左子节点），那么此时的A节点就是从根节点到B节点（B节点除外）路径上的一个节点的右子节点。（这里考虑了栈的大小和当前节点的深度）具体实现代码如下。（带注释）代码实现#定义二叉树节点。#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=Noneclass解决方案：defrecoverFromPreorder(self,S:str)->TreeNode:#使用栈辅助stack=[]s_length=len(S)i=0whilei
