Formatted question description: https://leetcode.ca/all/1028.html

1028. Recover a Tree From Preorder Traversal (Hard)

We run a preorder depth first search 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 S of this traversal, recover the tree and return its root.

Example 1:

Input: "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

Example 2:

Input: "1-2--3---4-5--6---7"
Output: [1,2,5,3,null,6,null,4,null,7]

Example 3:

Input: "1-401--349---90--88"
Output: [1,401,null,349,88,90]

Note:

The number of nodes in the original tree is between 1 and 1000.
Each node will have a value between 1 and 10^9.

Solution 1. Stack

// OJ: https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/
// Time: O(S)
// Space: O(H) where H is depth of tree
class Solution {
private:
    TreeNode *readNode(string &S, int &i) {
        int n = 0;
        for (; i < S.size() && isdigit(S[i]); ++i) n = 10 * n + S[i] - '0';
        return new TreeNode(n);
    }
    int readDash(string &S, int &i) {
        int cnt = 0;
        for (; i < S.size() && S[i] == '-'; ++i, ++cnt);
        return cnt;
    }
public:
    TreeNode* recoverFromPreorder(string S) {
        int i = 0, N = S.size();
        auto root = readNode(S, i);
        stack<TreeNode*> s;
        s.push(root);
        while (i < S.size()) {
            int dep = readDash(S, i);
            auto node = readNode(S, i);
            while (dep < s.size()) s.pop();
            auto p = s.top();
            if (p->left) p->right = node;
            else p->left = node;
            s.push(node);
        }
        return root;
    }
};

Solution 2. DFS

// OJ: https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/
// Time: O(S)
// Space: O(H)
class Solution {
    int curLevel;
    TreeNode *curNode;
    void dfs(istringstream &in, TreeNode *parent, int level) {
        if (in.eof()) return;
        curLevel = 0;
        for (; in.peek() == '-'; in.get(), ++curLevel);
        int n;
        in >> n;
        curNode = new TreeNode(n);
        while (curNode && curLevel == level) {
            if (!parent->left) parent->left = curNode;
            else parent->right = curNode;
            auto node = curNode;
            curNode = NULL;
            dfs(in, node, level + 1);
        }
    }
public:
    TreeNode* recoverFromPreorder(string S) {
        istringstream in(S);
        int n;
        in >> n;
        auto root = new TreeNode(n);
        dfs(in, root, 1);
        return root;
    }
};

/**
 * 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 S) {
        if (S == null || S.length() == 0)
            return null;
        StringBuffer sb = new StringBuffer(S);
        for (int i = S.length() - 1; i > 0; i--) {
            if (S.charAt(i) == '-' && S.charAt(i - 1) != '-')
                sb.insert(i, ',');
        }
        String[] array = sb.toString().split(",");
        int nodesCount = array.length;
        int rootVal = Integer.parseInt(array[0]);
        TreeNode root = new TreeNode(rootVal);
        if (nodesCount == 1)
            return root;
        Stack<TreeNode> nodeStack = new Stack<TreeNode>();
        Stack<Integer> levelStack = new Stack<Integer>();
        nodeStack.push(root);
        levelStack.push(0);
        for (int i = 1; i < nodesCount; i++) {
            String str = array[i];
            int level = str.lastIndexOf('-') + 1;
            int value = Integer.parseInt(str.substring(level));
            TreeNode node = new TreeNode(value);
            while (!levelStack.isEmpty() && levelStack.peek() >= level) {
                nodeStack.pop();
                levelStack.pop();
            }
            if (nodeStack.isEmpty())
                return null;
            TreeNode parent = nodeStack.peek();
            if (parent.left == null)
                parent.left = node;
            else if (parent.right == null)
                parent.right = node;
            else
                return null;
            nodeStack.push(node);
            levelStack.push(level);
        }
        return root;
    }
}

// OJ: https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/
// Time: O(S)
// Space: O(H) where H is depth of tree
class Solution {
private:
    TreeNode *readNode(string &S, int &i) {
        int n = 0;
        for (; i < S.size() && isdigit(S[i]); ++i) n = 10 * n + S[i] - '0';
        return new TreeNode(n);
    }
    int readDash(string &S, int &i) {
        int cnt = 0;
        for (; i < S.size() && S[i] == '-'; ++i, ++cnt);
        return cnt;
    }
public:
    TreeNode* recoverFromPreorder(string S) {
        int i = 0, N = S.size();
        auto root = readNode(S, i);
        stack<TreeNode*> s;
        s.push(root);
        while (i < S.size()) {
            int dep = readDash(S, i);
            auto node = readNode(S, i);
            while (dep < s.size()) s.pop();
            auto p = s.top();
            if (p->left) p->right = node;
            else p->left = node;
            s.push(node);
        }
        return root;
    }
};

# 1028. Recover a Tree From Preorder Traversal
# https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/

# 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, A: str) -> Optional[TreeNode]:
        stack = []
        n = len(A)
        index = 0
        
        while index < n:
            depth = 0
            
            while index < n and A[index] == '-':
                depth += 1
                index += 1
            
            val = 0
            while index < n and A[index].isdigit():
                val = val * 10 + int(A[index])
                index += 1

            while len(stack) > depth:
                stack.pop()
            
            node = TreeNode(val)
            
            if stack:
                if not stack[-1].left:
                    stack[-1].left = node
                else:
                    stack[-1].right = node
            
            stack.append(node)
        
        
        while len(stack) > 1:
            stack.pop()
        
        return stack.pop()

1028 - Recover a Tree From Preorder Traversal

1028. Recover a Tree From Preorder Traversal (Hard)

Solution 1. Stack

Solution 2. DFS

All Problems

All Solutions

Welcome to Subscribe On Youtube

1028. Recover a Tree From Preorder Traversal (Hard)

Solution 1. Stack

Solution 2. DFS

All Problems

All Solutions