609，从先序遍历还原二叉树
问题描述
来源：LeetCode第1028题
难度：困难
我们从二叉树的根节点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之间。
迭代方式解决
这题输入的是二叉树前序遍历的结果，让我们还原这颗二叉树。如果只给出二叉树的前序遍历结果我们是没法还原的。但这题还给出了两个条件，一个是每个数字前面的“-”表示当前节点的深度，一个是如果一个只有一个子节点，要保证这个子节点是左子节点。那么有了这两个条件，这颗二叉树基本上就能确定了。
我们看一下这题的解题思路：
首先创建一个栈，把创建的节点一个个压入到栈中。你会发现从栈底到栈顶每两个元素之间的关系是父子关系。画个图来看一下
通过上图我们可以发现从栈底到栈顶，1是2的父节点，2是3的父节点。其实还有一个最重要的发现就是栈中元素的个数-1就是栈顶元素的深度。这一个特性非常重要。这里要减1是因为树中节点的深度是从0开始的，不是从1开始，根节点的深度是0。
我们创建每个节点的时候，需要找到他的父节点，然后才能把当前节点挂到他的父节点下面。怎么找呢，就是通过栈中元素的个数来确定。看到这里估计代码大家都已经能写出来了，这里我们先来分开写。
第一步，找出当前节点的深度
//找出当前数字的深度，从0开始的，根节点是第0层
int level = 0;
while (S.charAt(i) == '-') {
level++;
i++;
}
第二步，找出当前节点的值
//找出当前节点的值
int val = 0;
while (i < S.length() && S.charAt(i) != '-') {
val = val * 10 + (S.charAt(i) - '0');
i++;
}
第三步，找出当前节点的父节点，我们上面分析过，栈中元素的个数-1就栈顶节点的深度。这里一直循环，当栈中元素个数等于level的时候，说明栈顶元素就是当前节点的父节点。
//找到当前节点的父节点，子节点的深度要比父节点大1
while (stack.size() > level) {
stack.pop();
}
第四步，把当前节点挂到父节点的下面，题中说了如果只有一个子节点，那么这个子节点就是左子节点。这里还要注意的是根节点是没有父节点的。
//创建当前结点
TreeNode node = new TreeNode(val);
//栈为空说明当前节点是根节点，如果栈不为空，说明
//当前节点不是空节点，需要把当前节点挂到他父节点
//的下面
if (!stack.isEmpty()) {
//如果节点只有一个子节点，那么保证该子节点为左子节点。
if (stack.peek().left == null) {
stack.peek().left = node;
} else {
//如果左子节点不为空，就放到右子节点中
stack.peek().right = node;
}
}
//把当前节点压入栈
stack.add(node);
通过上面我们把代码一步步拆解完之后我们再来看下完整代码。
public TreeNode recoverFromPreorder(String S) {
Stack<TreeNode> stack = new Stack<>();
for (int i = 0; i < S.length(); ) {
//找出当前数字的深度，从0开始的，根节点是第0层
int level = 0;
while (S.charAt(i) == '-') {
level++;
i++;
}
//找出当前节点的值
int val = 0;
while (i < S.length() && S.charAt(i) != '-') {
val = val * 10 + (S.charAt(i) - '0');
i++;
}
//找到当前节点的父节点，子节点的深度要比父节点大1
while (stack.size() > level) {
stack.pop();
}
//创建当前结点
TreeNode node = new TreeNode(val);
//栈为空说明当前节点是根节点，如果栈不为空，说明
//当前节点不是空节点，需要把当前节点挂到他父节点
//的下面
if (!stack.isEmpty()) {
//如果节点只有一个子节点，那么保证该子节点为左子节点。
if (stack.peek().left == null) {
stack.peek().left = node;
} else {
//如果左子节点不为空，就放到右子节点中
stack.peek().right = node;
}
}
//把当前节点压入栈
stack.add(node);
}
//除了根节点，其他子节点全部出栈
while (stack.size() > 1) {
stack.pop();
}
//返回根节点
return stack.pop();
}
把字符串拆开
题中说了节点是通过分隔符"-"隔开的，所以我们可以按照"-"把字符串拆开
//通过"-"分隔符把字符串拆开
String[] nodeValues = S.split("-");
这里不需要使用栈，我们可以使用一个list集合存储每层的节点，注意，每层只存储一个节点。我们直接可以通过get方法获取当前节点的父节点，也就是
TreeNode parent = list.get(level - 1);这里大家可能有点困惑，每层那么多节点我们只存储一个，会不会把之前的给覆盖掉啊，其实会覆盖掉的，但没关系，如果被覆盖掉了，说明覆盖掉的节点以及他的子节点和子子节点……都已经被访问完了。我们不需要再访问了。
比如下面图中红色的节点3在第二层，当遍历到他的时候，就会把第二层的节点2给覆盖掉，覆盖掉了也没关系，因为节点2及他下面的所有子节点都已经被访问完了。
搞懂了上面的分析过程我们再来看下代码
public TreeNode recoverFromPreorder(String S) {
//通过"-"分隔符把字符串拆开
String[] nodeValues = S.split("-");
List<TreeNode> list = new ArrayList<>();
//数组中的第一个值肯定是根节点，创建根节点然后添加到list中
list.add(new TreeNode(Integer.valueOf(nodeValues[0])));
//上面根节点已经加入到list中了，下面都是非根节点
int level = 1;
for (int i = 1; i < nodeValues.length; i++) {
if (!nodeValues[i].isEmpty()) {
TreeNode node = new TreeNode(Integer.valueOf(nodeValues[i]));
//因为是前序遍历，每层我们只需要存储一个结点即可，这个节点值有可能
//会被覆盖，如果被覆盖了说明这个节点以及他的子节点都以及遍历过了，
//所以我们不用考虑被覆盖问题
list.add(level, node);
//获取父节点
TreeNode parent = list.get(level - 1);
//左子节点为空，优先添加到左子节点中
if (parent.left == null) {
parent.left = node;
} else {
parent.right = node;
}
//深度要重新赋值
level = 1;
} else {
//统计节点的深度
level++;
}
}
//返回树的根节点
return list.get(0);
}
截止到目前我已经写了600多道算法题了，为了方便大家阅读，我把部分算法题整理成了pdf文档，目前有1000多页，大家可以在公众号中回复关键字“pdf”即可获取下载链接。