Reference: LeetCode
Difficulty: Hard

Problem

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
2
Input: "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

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

Analysis

Methods:

  1. Recursion
    • Do an iterative depth first search, parsing dashes from the string to know how to link the nodes together.
    • Be careful of the corner cases.
    • The value may consist of several digits.
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      private int index = 0;

      public TreeNode recoverFromPreorder(String s) {
        index = 0;
        return construct(s, 0);
      }

      // 1-2--3--4-5--6--7
      // 
      private TreeNode construct(String s, int depth) {
        // parse dash
        int numDash = 0;
        // index is pointing to the first "-"
        // E.g. root = 1, in this case, numDash is 0
        while (index + numDash < s.length() && s.charAt(index + numDash) == '-') {
          numDash += 1;
        }

        // base case
        if (numDash != depth) { // go back (backtracking)
          return null;
        }
        
        int valLength = 0; // index + numDash is pointing to the first digit
        while (index + numDash + valLength < s.length() && s.charAt(index + numDash + valLength) != '-') {
          valLength += 1;
        }
        String subStr = s.substring(index + numDash, index + numDash + valLength); // [x, x + len)
        int rootVal = Integer.parseInt(subStr);
        
        TreeNode root = new TreeNode(rootVal);

        index += numDash + valLength; // update index
        
        root.left = construct(s, depth + 1);
        root.right = construct(s, depth + 1);

        return root;
      }
      Time: $O(S)$ where $S$ is the length of the string.
      Space: $O(h)$