LeetCode 1028: Recover a Tree From Preorder Traversal (Depth Parsing + Stack Parent Linking)
LeetCode 1028Binary TreeStackToday we solve LeetCode 1028 - Recover a Tree From Preorder Traversal.
Source: https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/
English
Problem Summary
The preorder string uses dashes to encode depth and numbers to encode node values. Rebuild the original binary tree where depth d nodes must attach under depth d-1 nodes, and if a node has only one child, it is always the left child.
Key Insight
Each parsed token is (depth, value). Maintain a stack representing the current root-to-node path. Before inserting a new node at depth d, pop until stack size is d. Then the top is its parent.
Algorithm
- Parse consecutive dashes as depth, then parse digits as value.
- Create the node.
- While stack size > depth, pop.
- If stack is not empty, attach node to parent's left if empty, otherwise to right.
- Push node into stack.
- The first node is root.
Complexity Analysis
Let n be traversal length.
Time: O(n).
Space: O(h) for stack, worst case O(n).
Common Pitfalls
- Forgetting to pop back to exact parent depth.
- Incorrectly attaching right child before left child.
- Parsing multi-digit numbers as separate nodes.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* 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) {
int i = 0, n = traversal.length();
Deque<TreeNode> stack = new ArrayDeque<>();
while (i < n) {
int depth = 0;
while (i < n && traversal.charAt(i) == '-') {
depth++;
i++;
}
int val = 0;
while (i < n && Character.isDigit(traversal.charAt(i))) {
val = val * 10 + (traversal.charAt(i) - '0');
i++;
}
TreeNode node = new TreeNode(val);
while (stack.size() > depth) {
stack.pop();
}
if (!stack.isEmpty()) {
TreeNode parent = stack.peek();
if (parent.left == null) parent.left = node;
else parent.right = node;
}
stack.push(node);
}
while (stack.size() > 1) stack.pop();
return stack.peek();
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func recoverFromPreorder(traversal string) *TreeNode {
n := len(traversal)
i := 0
stack := []*TreeNode{}
for i < n {
depth := 0
for i < n && traversal[i] == '-' {
depth++
i++
}
val := 0
for i < n && traversal[i] >= '0' && traversal[i] <= '9' {
val = val*10 + int(traversal[i]-'0')
i++
}
node := &TreeNode{Val: val}
for len(stack) > depth {
stack = stack[:len(stack)-1]
}
if len(stack) > 0 {
parent := stack[len(stack)-1]
if parent.Left == nil {
parent.Left = node
} else {
parent.Right = node
}
}
stack = append(stack, node)
}
return stack[0]
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* recoverFromPreorder(string traversal) {
int i = 0, n = traversal.size();
vector<TreeNode*> st;
while (i < n) {
int depth = 0;
while (i < n && traversal[i] == '-') {
depth++;
i++;
}
int val = 0;
while (i < n && isdigit(traversal[i])) {
val = val * 10 + (traversal[i] - '0');
i++;
}
TreeNode* node = new TreeNode(val);
while ((int)st.size() > depth) st.pop_back();
if (!st.empty()) {
TreeNode* parent = st.back();
if (!parent->left) parent->left = node;
else parent->right = node;
}
st.push_back(node);
}
return st.front();
}
};# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:
n = len(traversal)
i = 0
stack = []
while i < n:
depth = 0
while i < n and traversal[i] == '-':
depth += 1
i += 1
val = 0
while i < n 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]/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {string} traversal
* @return {TreeNode}
*/
var recoverFromPreorder = function(traversal) {
const n = traversal.length;
let i = 0;
const stack = [];
while (i < n) {
let depth = 0;
while (i < n && traversal[i] === '-') {
depth++;
i++;
}
let val = 0;
while (i < n && traversal[i] >= '0' && traversal[i] <= '9') {
val = val * 10 + (traversal.charCodeAt(i) - 48);
i++;
}
const node = new TreeNode(val);
while (stack.length > depth) {
stack.pop();
}
if (stack.length > 0) {
const parent = stack[stack.length - 1];
if (parent.left === null) parent.left = node;
else parent.right = node;
}
stack.push(node);
}
return stack[0];
};中文
题目概述
给定一个先序遍历字符串，连续的 - 数量表示节点深度，后面的数字表示节点值。请把原始二叉树还原出来。题目还保证若某节点只有一个孩子，则该孩子一定是左孩子。
核心思路
把每个节点解析成 (depth, value)。用栈维护“当前路径”。处理新节点前，先弹栈到长度等于它的深度，这样栈顶就是它的父节点，然后按“先左后右”挂接。
算法步骤
- 统计连续 - 得到深度 depth，再读取连续数字得到 value。
- 创建当前节点。
- 当栈长度大于 depth 时持续弹栈。
- 若栈非空，优先挂到父节点左子树，否则挂到右子树。
- 把当前节点入栈。
- 第一个节点就是根节点。
复杂度分析
设字符串长度为 n。
时间复杂度：O(n)。
空间复杂度：栈为 O(h)，最坏 O(n)。
常见陷阱
- 没有弹到正确深度，导致父子关系错位。
- 忽略“单孩子一定是左孩子”的挂接顺序。
- 把多位数字拆成多个节点。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* 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) {
int i = 0, n = traversal.length();
Deque<TreeNode> stack = new ArrayDeque<>();
while (i < n) {
int depth = 0;
while (i < n && traversal.charAt(i) == '-') {
depth++;
i++;
}
int val = 0;
while (i < n && Character.isDigit(traversal.charAt(i))) {
val = val * 10 + (traversal.charAt(i) - '0');
i++;
}
TreeNode node = new TreeNode(val);
while (stack.size() > depth) {
stack.pop();
}
if (!stack.isEmpty()) {
TreeNode parent = stack.peek();
if (parent.left == null) parent.left = node;
else parent.right = node;
}
stack.push(node);
}
while (stack.size() > 1) stack.pop();
return stack.peek();
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func recoverFromPreorder(traversal string) *TreeNode {
n := len(traversal)
i := 0
stack := []*TreeNode{}
for i < n {
depth := 0
for i < n && traversal[i] == '-' {
depth++
i++
}
val := 0
for i < n && traversal[i] >= '0' && traversal[i] <= '9' {
val = val*10 + int(traversal[i]-'0')
i++
}
node := &TreeNode{Val: val}
for len(stack) > depth {
stack = stack[:len(stack)-1]
}
if len(stack) > 0 {
parent := stack[len(stack)-1]
if parent.Left == nil {
parent.Left = node
} else {
parent.Right = node
}
}
stack = append(stack, node)
}
return stack[0]
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* recoverFromPreorder(string traversal) {
int i = 0, n = traversal.size();
vector<TreeNode*> st;
while (i < n) {
int depth = 0;
while (i < n && traversal[i] == '-') {
depth++;
i++;
}
int val = 0;
while (i < n && isdigit(traversal[i])) {
val = val * 10 + (traversal[i] - '0');
i++;
}
TreeNode* node = new TreeNode(val);
while ((int)st.size() > depth) st.pop_back();
if (!st.empty()) {
TreeNode* parent = st.back();
if (!parent->left) parent->left = node;
else parent->right = node;
}
st.push_back(node);
}
return st.front();
}
};# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:
n = len(traversal)
i = 0
stack = []
while i < n:
depth = 0
while i < n and traversal[i] == '-':
depth += 1
i += 1
val = 0
while i < n 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]/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {string} traversal
* @return {TreeNode}
*/
var recoverFromPreorder = function(traversal) {
const n = traversal.length;
let i = 0;
const stack = [];
while (i < n) {
let depth = 0;
while (i < n && traversal[i] === '-') {
depth++;
i++;
}
let val = 0;
while (i < n && traversal[i] >= '0' && traversal[i] <= '9') {
val = val * 10 + (traversal.charCodeAt(i) - 48);
i++;
}
const node = new TreeNode(val);
while (stack.length > depth) {
stack.pop();
}
if (stack.length > 0) {
const parent = stack[stack.length - 1];
if (parent.left === null) parent.left = node;
else parent.right = node;
}
stack.push(node);
}
return stack[0];
};
Comments