LeetCode 题解工作台
从先序遍历还原二叉树
我们从二叉树的根节点 root 开始进行深度优先搜索。 在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（ 如果节点的深度为 D ，则其直接子节点的深度为 D + 1 。根节点的深度为 0 ）。 如果节点只有一个子节点，那么保证该子节点为左子节点。 给出…
4
题型
4
代码语言
3
相关题
当前训练重点
困难 · 二分·树·traversal
答案摘要
/ * Definition for a binary tree node.
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
我们从二叉树的根节点 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之间。
解题思路
方法一
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode recoverFromPreorder(String traversal) {
Stack<TreeNode> stack = new Stack<>();
int i = 0;
while (i < traversal.length()) {
int depth = 0;
while (i < traversal.length() && traversal.charAt(i) == '-') {
depth++;
i++;
}
int num = 0;
while (i < traversal.length() && Character.isDigit(traversal.charAt(i))) {
num = num * 10 + (traversal.charAt(i) - '0');
i++;
}
// Create the new node
TreeNode newNode = new TreeNode(num);
while (stack.size() > depth) {
stack.pop();
}
if (!stack.isEmpty()) {
if (stack.peek().left == null) {
stack.peek().left = newNode;
} else {
stack.peek().right = newNode;
}
}
stack.push(newNode);
}
return stack.isEmpty() ? null : stack.get(0);
}
}
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because we parse each character and node once. Space complexity is O(n) due to the stack holding up to all nodes along a path, which is essential to reconstruct the tree correctly. |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Ask if the candidate handles single-child nodes correctly as left children.
- question_mark
Check if the solution correctly counts dashes to determine node depth.
- question_mark
Watch for proper use of a stack or similar structure to maintain current ancestors.
常见陷阱
外企场景- error
Miscounting dashes and attaching nodes to the wrong parent depth.
- error
Assuming right children when a node has only one child, breaking tree structure.
- error
Pushing all nodes onto the stack without popping ancestors, leading to incorrect hierarchy.
进阶变体
外企场景- arrow_right_alt
Recover tree from a preorder string with variable-length integers and missing children indicated explicitly.
- arrow_right_alt
Construct a tree from a preorder sequence where some nodes may be skipped or null explicitly.
- arrow_right_alt
Recover a binary tree while returning the result as a nested dictionary instead of array representation.