# 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) -> TreeNode:
stack = []
i = 0
n = len(traversal)
while i < n:
depth = 0
# Count dashes to determine depth
while i < n and traversal[i] == '-':
depth += 1
i += 1
# Read the node value
val = 0
while i < n and traversal[i].isdigit():
val = val * 10 + int(traversal[i])
i += 1
node = TreeNode(val)
# If stack length is greater than depth, pop to parent
while len(stack) > depth:
stack.pop()
# Attach to parent if exists
if stack:
if not stack[-1].left:
stack[-1].left = node
else:
stack[-1].right = node
stack.append(node)
return stack[0]
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* recoverFromPreorder(string traversal) {
vector<TreeNode*> stack;
int i = 0, n = traversal.size();
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 (stack.size() > depth) stack.pop_back();
if (!stack.empty()) {
if (!stack.back()->left) stack.back()->left = node;
else stack.back()->right = node;
}
stack.push_back(node);
}
return stack[0];
}
};
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode recoverFromPreorder(String traversal) {
Deque<TreeNode> stack = new ArrayDeque<>();
int i = 0, n = traversal.length();
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()) {
if (stack.peek().left == null) stack.peek().left = node;
else stack.peek().right = node;
}
stack.push(node);
}
while (stack.size() > 1) stack.pop();
return stack.peek();
}
}
/**
* 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) {
let stack = [];
let i = 0, n = traversal.length;
while (i < n) {
let depth = 0;
while (i < n && traversal[i] === '-') {
depth++;
i++;
}
let val = 0;
while (i < n && /\d/.test(traversal[i])) {
val = val * 10 + Number(traversal[i]);
i++;
}
let node = new TreeNode(val);
while (stack.length > depth) stack.pop();
if (stack.length) {
if (!stack[stack.length - 1].left)
stack[stack.length - 1].left = node;
else
stack[stack.length - 1].right = node;
}
stack.push(node);
}
return stack[0];
};
Given a string traversal representing the preorder traversal of a binary tree, recover the tree and return its root. In this representation:
'-' before its value.There is exactly one valid binary tree that can be reconstructed from the given traversal string.
To solve this problem, we need to interpret the preorder traversal string and reconstruct the binary tree structure. The dashes tell us how deep in the tree a node is. For example, a node with two dashes before its value is a child of a node with one less dash.
A brute-force approach might involve parsing the string and recursively trying to attach nodes at the right depth, but this can get complicated and inefficient. Instead, we can use a stack to keep track of the current path from the root to the latest node, allowing us to efficiently determine where to attach each new node as we parse the string.
The key insight is that as we move through the string, the number of dashes tells us whether we need to go up (pop from the stack) or down (add a child) in the tree structure.
We will reconstruct the tree using a stack to track the path from the root to the current node. Here's how:
This approach works efficiently because each node is processed exactly once, and the stack always represents the current path in the tree.
Let's walk through an example with traversal = "1-2--3--4-5--6--7":
The final tree is:
1
/ \
2 5
/ \ / \
3 4 6 7
Brute-force approach: If you tried to recursively search for the correct parent for each node, you could end up with O(N^2) time if you traverse up the tree for every node.
Optimized stack approach (as above):
By carefully parsing the traversal string and using a stack to keep track of the current path, we can efficiently reconstruct the binary tree in a single pass. The key insight is that the number of dashes tells us the depth, and the stack helps us quickly find the correct parent for each node. This method is both elegant and efficient, making it ideal for this problem.