1028. Recover a Tree From Preorder Traversal

T: O(n)

S: O(n)

/**
 * 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("nodeVal=" + nodeVal + ",level=" + level + ",nodeLevel=" + nodeLevel);
        if (level != nodeLevel) { // for right level to add node, so if it try to add node in wrong level, will return, then backtracking
        // until it matches the correct level!
            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 


new ex: (see this)
"1-2--3-4"
nodeVal=1,level=0,nodeLevel=0
nodeVal=2,level=1,nodeLevel=1
nodeVal=3,level=2,nodeLevel=2
nodeVal=4,level=3,nodeLevel=1 -> this is level != nodeLevel so return null, back to previous level, index[0] keeps the same
nodeVal=4,level=3,nodeLevel=1 -> this is level != nodeLevel so return null, back to previous level, index[0] keeps the same
nodeVal=4,level=2,nodeLevel=1 -> this is level != nodeLevel so return null, back to previous level, index[0] keeps the same
nodeVal=4,level=1,nodeLevel=1 -> finally it gets the correct level! so connect this node! (and because index[0] is the same, so we'll try to keep using it!)

 1 level = nodeLevel = 0
 /
 2 level = nodeLevel = 1    4 (add here)
/
3. level = nodeLevel = 2, 
/
level = 3
then try level + 1 -> try nodeVal=4,level=3,nodeLevel=1 -> x back to previous level
level = 2 -> x back to previous level
nodeVal=4,level=1,nodeLevel = 1 -> correct!

like these:
nodeVal=4,level=3,nodeLevel=1 -> this is level != nodeLevel so return null, back to previous level, index[0] keeps the same
nodeVal=4,level=3,nodeLevel=1 -> this is level != nodeLevel so return null, back to previous level, index[0] keeps the same
nodeVal=4,level=2,nodeLevel=1 -> this is level != nodeLevel so return null, back to previous level, index[0] keeps the same
nodeVal=4,level=1,nodeLevel=1 -> finally it gets the correct level! so connect this node! (and because index[0] is the same, so we'll try to

        int[] cur = list.get(index[0]);
        int nodeVal = cur[0];
        int nodeLevel = cur[1];
        //System.out.println("nodeVal=" + nodeVal + ",level=" + level + ",nodeLevel=" + nodeLevel);
        if (level != nodeLevel) { // for right level to add node, so if it try to add node in wrong level, will return, then backtracking
        // until it matches the correct level!
            return null;
        }
        TreeNode root = new TreeNode(nodeVal);
        index[0]++; 
        root.left = dfs(list, index, nodeLevel+1); 
        root.right = dfs(list, index, nodeLevel+1); 


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