1093. Recover A Tree From Preorder Traversal¶

LeetCode Problem View on GitHub

1093. Recover a Tree From Preorder Traversal

Hard

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:

• The number of nodes in the original tree is in the range [1, 1000].
• 1 <= Node.val <= 109

Solution¶

class Solution {
    public TreeNode recoverFromPreorder(String S) {
        int n = S.length();
        HashMap<Integer, TreeNode> map = new HashMap<>();
        int i = 0;
        while(i < n) {
            int curLevel = 0, num = 0;
            while(i < S.length() && S.charAt(i) == '-') {
                ++curLevel;
                ++i;
            }
            while(i < n && S.charAt(i) >= '0' && S.charAt(i) <= '9') {
                num = num * 10 + (S.charAt(i) - '0');
                i++;
            }
            TreeNode current = new TreeNode(num);
            map.put(curLevel, current);
            if(curLevel > 0) {
                TreeNode parent = map.get(curLevel - 1);
                if(parent.left == null) parent.left = current;
                else parent.right = current;
            }
        }
        return map.get(0);
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here