原题
我们从二叉树的根节点 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之间。
解法
思想
好感动。。我也只能写得出这样的困难题了。
用栈来模拟DFS的过程，并记录当前节点的深度和上一个节点的深度，如果当前节点的深度 = 上一个节点的深度+1，那么说明当前节点是上一个节点的子节点，否则需要将栈中的元素弹出。
代码
class Solution {
public TreeNode recoverFromPreorder(String S) {
Stack<TreeNode> stack = new Stack<>();
int num = 0;
int prevDepth = -1;
int depth = 0;
char[] chars = S.toCharArray();
TreeNode root = null;
for(int i = 0;i<chars.length;i++){
// 是数字
if(Character.isDigit(chars[i])){
num = num*10+(chars[i]-'0');
// 若是一个数字的结尾字符
if(i==chars.length-1 || !Character.isDigit(chars[i+1])){
TreeNode node = new TreeNode(num);
// 如果depth为0，记录当前节点为根节点
if(depth == 0) root = node;
// 如果depth不等于prevDepth+1，说明该节点不是上一个节点的子节点，需要从栈中弹出相应的元素个数
if(depth != prevDepth + 1){
for(int n = 0;n<prevDepth+1-depth;n++)
stack.pop();
}
// 将该节点添加到上一个节点的子节点
if(!stack.isEmpty()){
TreeNode prev = stack.peek();
if(prev.left == null){
prev.left = node;
}else prev.right = node;
}
stack.push(node);
num = 0;
prevDepth = depth;
depth = 0;
}
}
// 是中划线，深度+1
else depth ++;
}
return root;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode1028-%e4%bb%8e%e5%85%88%e5%ba%8f%e9%81%8d%e5%8e%86%e8%bf%98%e5%8e%9f%e4%ba%8c%e5%8f%89%e6%a0%91/
