1028. Recover a Tree From Preorder Traversal.md

1028. Recover a Tree From Preorder Traversal

---

leetcode-cn Daily Challenge on June 18, 2020.

---

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

• mine

  • Java

    • DFS & List Runtime: 3 ms, faster than 77.74%, Memory Usage: 39.5 MB, less than 36.00% of Java online submissions

      //Time O(S), Space O(N)
      
      //当前需要定位的节点索引
      public int nodeIndex = 1;
      
      public TreeNode recoverFromPreorder(String S) {
          List<Integer> decodeRes = decodeString(S);
          TreeNode res = new TreeNode(decodeRes.get(1));
          dfs(res, decodeRes, 0);
          return res;
      }
      private int dfs(TreeNode node, List<Integer> decodeRes, int beforeDepth) {
          int index = 2 * nodeIndex;
          if (index + 1 > decodeRes.size()) {
              return -1;
          }
          int depth = decodeRes.get(index);
          int returnDepth = depth;
          if (depth == beforeDepth + 1) {
              node.left = new TreeNode(decodeRes.get(index + 1));
              nodeIndex++;
              returnDepth = dfs(node.left, decodeRes, depth);
          }
          if (returnDepth == beforeDepth + 1) {
              node.right = new TreeNode(decodeRes.get(nodeIndex * 2 + 1));
              nodeIndex++;
              returnDepth = dfs(node.right, decodeRes, returnDepth);
          }
          return returnDepth;
      }
      //decode string return list,odd index is node depth,even index is node value.
      public List<Integer> decodeString(String S) {
          List<Integer> res = new ArrayList<>();
          res.add(0);
          int depth, val;
          for (int i = 0; i < S.length(); ) {
              for (depth = 0; S.charAt(i) == '-'; i++) {
                  depth++;
              }
              if (depth != 0) {
                  res.add(depth);
              }
              for (val = 0; i < S.length() && S.charAt(i) != '-'; i++) {
                  val = val * 10 + (S.charAt(i) - '0');
              }
              res.add(val);
          }
          return res;
      }
      

    • DFS & Map Runtime: 2 ms, faster than 92.47%, Memory Usage: 40 MB, less than 55.93% of Java online submissions

      // O(len(S))time O(len(S) + C + D)space
      // C is node's size   
      // D is tree depth
      public TreeNode recoverFromPreorder(String S) {
          if (S == null || S.length() == 0) {
              return null;
          }
          char[] arr = S.toCharArray();
          for (char c : arr) {
              if (c != '-' && (c < '0' || c > '9')) {
                  return null;
              }
          }
          Map<Integer, TreeNode> map = new HashMap<>();
          int i = S.indexOf('-');
          TreeNode res = null;
          if (i == -1) {
              return new TreeNode(Integer.parseInt(S));
          }
          helper(arr, map, 0, 0);
          return map.get(0);
      }
      
      void helper(char[] arr, Map<Integer, TreeNode> map, int start, int beforeDepth) {
          int depth = 0;
          while (start < arr.length && arr[start] == '-') {
              depth++;
              start++;
          }
          int num = 0;
          while (start < arr.length && arr[start] != '-') {
              num = num * 10 + (arr[start] - '0');
              start++;
          }
          TreeNode node = new TreeNode(num);
          if (depth > 0) {
              TreeNode parent = map.get(depth - 1);
              if (parent.left == null) {
                  parent.left = node;
              } else {
                  parent.right = node;
              }
          }
          map.put(depth, node);
          if (start != arr.length) {
              helper(arr, map, start, depth);
          }
      }
      

---

• the most votes
  • Stack Runtime: 4 ms, faster than 65.90%, Memory Usage: 39.6 MB, less than 36.00% of Java online submissions

    //Time O(S), Space O(N)
    public TreeNode recoverFromPreorder(String S) {
        int level, val;
        Stack<TreeNode> stack = new Stack<>();
        for (int i = 0; i < S.length();) {
            for (level = 0; S.charAt(i) == '-'; i++) {
                level++;
            }
            for (val = 0; i < S.length() && S.charAt(i) != '-'; i++) {
                val = val * 10 + (S.charAt(i) - '0');
            }
            while (stack.size() > level) {
                stack.pop();
            }
            TreeNode node = new TreeNode(val);
            if (!stack.isEmpty()) {
                if (stack.peek().left == null) {
                    stack.peek().left = node;
                } else {
                    stack.peek().right = node;
                }
            }
            stack.add(node);
        }
        while (stack.size() > 1) {
            stack.pop();
        }
        return stack.pop();
    }
    

---