1028. Recover a Tree From Preorder Traversal

T: O(n + list size)
S: O(list size)

/**
 * 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 {
    public TreeNode recoverFromPreorder(String traversal) {
        List<int[]> list = parseTraversal(traversal);
        int[] index = new int[1];
        return dfs(list, index, 0);
    }
    /**

1-2-3

1
/
2 

 */
    private TreeNode dfs(List<int[]> list, int[] index, int level) {
        if (index[0] == list.size()) {
            return null;
        }
        int[] cur = list.get(index[0]);
        int nodeVal = cur[0];
        int nodeLevel = cur[1];
        //System.out.println("from=" + from + ",nodeVal=" + nodeVal + ",level=" + level);
        if (level != nodeLevel) {
            return null;
        }
        TreeNode root = new TreeNode(nodeVal);
        index[0]++; 
        root.left = dfs(list, index, nodeLevel+1); 
        root.right = dfs(list, index, nodeLevel+1); 
        return root;
    }
    private List<int[]> parseTraversal(String s) {
        int i = 0;
        List<int[]> list = new ArrayList<>();
        int level = 0;
        while (i < s.length()) {
            if (Character.isDigit(s.charAt(i))) {
                StringBuilder sb = new StringBuilder();
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    sb.append(s.charAt(i));
                    i++;
                }
                list.add(new int[] {Integer.parseInt(sb.toString()), level});
            } else {
                level = 0;
                while (i < s.length() && !Character.isDigit(s.charAt(i))) {
                    level++;
                    i++;
                }
            }
        }
        return list;
    }
}

/***
for ex:
traversal =
"1-2-3"

should be 

 1
/ \
2. 3

Stdout
from=root,nodeVal=1,level=0
from=left,nodeVal=2,level=1. -> level1! 
from=left,nodeVal=3,level=2 
from=right,nodeVal=3,level=2 ->reach end!
from=right,nodeVal=3,level=1 -> then stack out, back to previous level1 -> so we can use level to find the correct level to insert!


T: O(n + list size)
S: O(list size)
 */