Hard
题目描述
我们从二叉树的根节点 root 开始进行深度优先搜索。
在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0。
如果节点只有一个子节点，那么保证该子节点为左子节点。
给出遍历输出 S，请你还原树并返回其根节点 root。
示例 1：
输入：traversal = "1-2--3--4-5--6--7"
输出：[1,2,5,3,4,6,7]
示例 2：
输入：traversal = "1-2--3---4-5--6---7"
输出：[1,2,5,3,null,6,null,4,null,7]
示例 3：
输入：traversal = "1-401--349---90--88"
输出：[1,401,null,349,88,90]
提示：
- 原始树中的节点数介于
1和1000之间。 - 每个节点的值介于
1和10^9之间。
解题思路
这道题的核心思路是模拟前序遍历的逆过程。我们需要根据短划线的数量来确定节点的深度，然后根据深度关系来构建二叉树。
解题思路：
解析字符串：首先需要将字符串解析成
(深度, 值)的形式。通过统计连续的短划线数量来确定深度。使用栈维护路径：由于是前序遍历，我们可以使用栈来维护从根节点到当前节点的路径。栈中存储的是各个深度的节点。
构建树的过程：
- 对于每个新节点，首先根据其深度调整栈的大小（弹出深度大于等于当前节点深度的节点）
- 然后将新节点作为栈顶节点的子节点
- 根据题目规定，如果父节点没有左子节点，新节点作为左子节点；否则作为右子节点
关键观察：由于是前序遍历且只有一个子节点时保证是左子节点，我们可以通过栈来准确确定父子关系。
时间复杂度分析：需要遍历整个字符串一次，每个节点最多进出栈一次，所以时间复杂度为 O(n)，其中 n 是字符串长度。
代码实现
class Solution {
public:
TreeNode* recoverFromPreorder(string traversal) {
stack<TreeNode*> stk;
int i = 0;
while (i < traversal.length()) {
// 计算深度（短划线数量）
int depth = 0;
while (i < traversal.length() && traversal[i] == '-') {
depth++;
i++;
}
// 解析节点值
int val = 0;
while (i < traversal.length() && isdigit(traversal[i])) {
val = val * 10 + (traversal[i] - '0');
i++;
}
TreeNode* node = new TreeNode(val);
// 调整栈，保持栈的大小等于深度
while (stk.size() > depth) {
stk.pop();
}
// 如果不是根节点，连接到父节点
if (!stk.empty()) {
TreeNode* parent = stk.top();
if (parent->left == nullptr) {
parent->left = node;
} else {
parent->right = node;
}
}
stk.push(node);
}
// 返回根节点
while (stk.size() > 1) {
stk.pop();
}
return stk.top();
}
};
class Solution:
def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:
stack = []
i = 0
while i < len(traversal):
# 计算深度（短划线数量）
depth = 0
while i < len(traversal) and traversal[i] == '-':
depth += 1
i += 1
# 解析节点值
val = 0
while i < len(traversal) and traversal[i].isdigit():
val = val * 10 + int(traversal[i])
i += 1
node = TreeNode(val)
# 调整栈，保持栈的大小等于深度
while len(stack) > depth:
stack.pop()
# 如果不是根节点，连接到父节点
if stack:
parent = stack[-1]
if parent.left is None:
parent.left = node
else:
parent.right = node
stack.append(node)
# 返回根节点
return stack[0]
public class Solution {
public TreeNode RecoverFromPreorder(string traversal) {
Stack<TreeNode> stack = new Stack<TreeNode>();
int i = 0;
while (i < traversal.Length) {
// 计算深度（短划线数量）
int depth = 0;
while (i < traversal.Length && traversal[i] == '-') {
depth++;
i++;
}
// 解析节点值
int val = 0;
while (i < traversal.Length && char.IsDigit(traversal[i])) {
val = val * 10 + (traversal[i] - '0');
i++;
}
TreeNode node = new TreeNode(val);
// 调整栈，保持栈的大小等于深度
while (stack.Count > depth) {
stack.Pop();
}
// 如果不是根节点，连接到父节点
if (stack.Count > 0) {
TreeNode parent = stack.Peek();
if (parent.left == null) {
parent.left = node;
} else {
parent.right = node;
}
}
stack.Push(node);
}
// 返回根节点
while (stack.Count > 1) {
stack.Pop();
}
return stack.Peek();
}
}
var recoverFromPreorder = function(traversal) {
const stack = [];
let i = 0;
while (i < traversal.length) {
// 计算深度（短划线数量）
let depth = 0;
while (i < traversal.length && traversal[i]
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 字符串解析 | O(n) | O(1) |
| 栈操作 | O(n) | O(h) |
| 总计 | O(n) | O(h) |
其中 n 是字符串长度，h 是树的高度。每个字符最多被访问常数次，每个节点最多进出栈一次，所以时间复杂度是线性的。空间复杂度主要由栈的深度决定，最坏情况下等于树的高度。