We run a preorder depth-first search (DFS) on the root of a binary tree.
At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node. If the depth of a node is D, the depth of its immediate child is D + 1. The depth of the root node is 0.
If a node has only one child, that child is guaranteed to be the left child.
Given the output traversal of this traversal, recover the tree and return its root.
Example 1:
Input: traversal = "1-2--3--4-5--6--7" Output: [1,2,5,3,4,6,7]
Example 2:
Input: traversal = "1-2--3---4-5--6---7" Output: [1,2,5,3,null,6,null,4,null,7]
Example 3:
Input: traversal = "1-401--349---90--88" Output: [1,401,null,349,88,90]
Constraints:
[1, 1000].1 <= Node.val <= 109In this approach, we recursively parse the traversal string to construct the tree. We track the current position in the string and the expected depth using recursion. For each valid node, we create a new tree node and attempt to construct its left and right subtrees by increasing the expected depth.
The code defines a TreeNode class and a recoverFromPreorder function that constructs a binary tree from the given traversal string. This is done using a nested helper function that recursively builds the tree. The function uses a nonlocal index variable to maintain the current position within the string.
For each node, helper checks the number of dashes to see if they match the expected depth. If they match, it extracts the number representing the node's value, creates a TreeNode, and attempts to add left and right children by increasing the expected depth.
C++
Java
Time Complexity: O(n), where n is the length of the traversal string, since each character is processed once.
Space Complexity: O(h), where h is the height of the tree, as this is the maximum depth of the recursion stack.
An iterative approach can be implemented using a stack. We use the stack to keep track of nodes along with their depths, and iteratively add nodes while maintaining the correct parent-child relationships. Each new node is inserted as a child of the node on the top of the stack, with adjustments made based on depths.
In Python, an iterative solution uses a stack to manage nodes and depths while parsing the traversal string. The number of dashes determines the depth. Nodes are created based on parsed values, and the stack is leveraged to attach each node at the correct position in the tree. Levels deeper than the current node's depth are popped from the stack, associating nodes as the left (and subsequently right) child of the last valid node at that depth.
C#
JavaScript
Time Complexity: O(n), where n is the string length, as each character is evaluated once.
Space Complexity: O(h), where h is the height of the tree, related to the maximum size of the stack.
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(n), where n is the length of the traversal string, since each character is processed once. Space Complexity: O(h), where h is the height of the tree, as this is the maximum depth of the recursion stack. |
| Iterative Approach Using Stack | Time Complexity: O(n), where n is the string length, as each character is evaluated once. Space Complexity: O(h), where h is the height of the tree, related to the maximum size of the stack. |
Construct Binary Tree from Inorder and Preorder Traversal - Leetcode 105 - Python • NeetCode • 307,238 views views
Watch 9 more video solutions →Practice Recover a Tree From Preorder Traversal with our built-in code editor and test cases.
Practice on FleetCode