题目简介：
我们从二叉树的根节点 root 开始进行深度优先搜索。
在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。
如果节点只有一个子节点，那么保证该子节点为左子节点。
给出遍历输出 S，还原树并返回其根节点 root。
示例 1：
1
2
| 输入："1-2--3--4-5--6--7"
输出：[1,2,5,3,4,6,7]
|
示例 2：
1
2
| 输入："1-2--3---4-5--6---7"
输出：[1,2,5,3,null,6,null,4,null,7]
|
思路：
利用栈存储节点以及相应的深度。将遍历中遇到的节点及相应的深度依次入栈。
每有一个-，节点的深度就 +1，设当前的节点为node，深度为depth，则node的父节点的深度必为depth - 1。所以每次从栈中弹出数据(即之前所遍历到的节点)，直到栈顶元素的深度为depth - 1，此节点便为父节点。
找到父节点后，由于节点只有一个子节点时，那么保证该子节点为左子节点。所以优先设置子节点为父节点的左节点，若已有左节点，则设置为右节点。
tip:
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
class Solution {
public:
TreeNode* recoverFromPreorder(string S) {
stack<pair<TreeNode*, int>> stk;
int root_num = 0;
int i = 0;
while(i < S.length() && S[i] != '-'){
root_num = root_num * 10 + S[i] - '0';
i++;
}
TreeNode* root = new TreeNode(root_num);
stk.push(make_pair(root, 0));
while(i < S.length()){
int depth = 0;
while(i < S.length() && S[i] == '-'){
depth++;
i++;
}
int num = 0;
while(i < S.length() && S[i] != '-'){
num = num * 10 + S[i] - '0';
i++;
}
TreeNode* node = new TreeNode(num);
while(!stk.empty()){
auto top_node = stk.top();
if(depth != top_node.second + 1){
stk.pop();
}
else{
if(top_node.first -> left == NULL)
top_node.first -> left = node;
else
top_node.first -> right = node;
stk.push(make_pair(node, depth));
break;
}
}
}
return root;
}
};
|
