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 S of this traversal, recover the tree and return its root.

Example 1:

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

Example 2:

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

Example 3:

Input: S = "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

/**
 * 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 {
    private int index;
    
    public TreeNode recoverFromPreorder(String S) {
        index = 0;
        return recover(S, 0);
    }
    
    private TreeNode recover(String S, int depth) {
        if (index == S.length()) {
            return null;
        }
        int currIndex = index;
        int level = readNextLevel(S);
        if (level != depth) {
            index = currIndex;
            return null;
        }
        int val = readNextVal(S);
        TreeNode node = new TreeNode(val);
        node.left = recover(S, depth + 1);
        node.right = recover(S, depth + 1);
        return node;
    }
    
    private int readNextLevel(String S) {
        int level = 0;
        while (index < S.length() && S.charAt(index) == '-') {
            level++;
            index++;
        }
        return level;
    }
    
    private int readNextVal(String S) {
        int val = 0;
        while (index < S.length() && S.charAt(index) != '-') {
            val = val * 10 + (S.charAt(index) - '0');
            index++;
        }
        return val;
    }
}
class Solution {
    int index = 0;
    public TreeNode recoverFromPreorder(String S) {
        return helper(S, 0);
    }
    
    public TreeNode helper(String s, int depth) {
        int numDash = 0;
        while (index + numDash < s.length() && s.charAt(index + numDash) == '-') {
            numDash++;
        }
        if (numDash != depth) return null;
        int next = index + numDash;
        while (next < s.length() && s.charAt(next) != '-') next++;
        int val = Integer.parseInt(s.substring(index + numDash, next));
        index = next;
        TreeNode root = new TreeNode(val);
        root.left = helper(s, depth + 1);
        root.right = helper(s, depth + 1);
        return root;
    }
}
/**
 * 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;
 *     }
 * }
 */

// Sangam
class Solution {
    
    String S = null;
    int index = 0;
    Integer nextNodeValue = null;
    int nextHeight = 0;
    public TreeNode recoverFromPreorder(String S) {
        if (S.isEmpty()) return null;
        
        this.S = S;
        this.setNextNodeValue();
        TreeNode root = new TreeNode(nextNodeValue);
        
        recoverFromPreorder(nextHeight + 1, root);
        return root;
        
    }
    
    public void recoverFromPreorder(int currentHeight, TreeNode root) {
        
        this.setNextHeight();
        this.setNextNodeValue();
        
        
        if (currentHeight > this.nextHeight) return;
        root.left = new TreeNode(nextNodeValue);
        recoverFromPreorder(currentHeight + 1, root.left);
        
        
        if (currentHeight > this.nextHeight) return;
        root.right = new TreeNode(nextNodeValue);
        recoverFromPreorder(currentHeight + 1, root.right);
    }
    
    public void setNextHeight() {
        int height = 0;
        while (index < S.length()) {
            char ch = S.charAt(index);
            if (ch == '-') {
                height++; 
                index++;
                continue;
            }
            break;
        }
        nextHeight = height;
    }
    
    public void setNextNodeValue() {
        StringBuilder sb = new StringBuilder();
        while (index < S.length() && S.charAt(index) != '-') {
            sb.append(S.charAt(index));
            index++;
        }
        if (sb.length() == 0) return;
        nextNodeValue = Integer.parseInt(sb.toString());
    }
}

Leave a reply