解法一

参考了评论区的思路。先解析字符串，提取每个结点的信息，然后按顺序建树，根据深度信息判断是否进一步建立子结点。
也可以一边遍历一边解析字符串，总体类似。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     // 结点深度队列
  12.     private Queue<Integer> depthQueue;
  13.     // 结点数值队列
  14.     private Queue<Integer> numQueue;
  16.     public TreeNode recoverFromPreorder(String S) {
  17.         depthQueue = new LinkedList<>();
  18.         numQueue = new LinkedList<>();
  19.         // 当前结点的深度信息在S中的起始下标
  20.         int depthHead = 0;
  21.         for (int i = 0; i < S.length(); ) {
  22.             // 解析深度
  23.             while (S.charAt(i) == '-') {
  24.                 ++i;
  25.             }
  26.             depthQueue.offer(i - depthHead);
  28.             // 解析数值
  29.             int num = 0;
  30.             while ((i < S.length()) && (S.charAt(i) != '-')) {
  31.                 num = num * 10 + S.charAt(i) - 48;
  32.                 ++i;
  33.             }
  34.             numQueue.offer(num);
  35.             depthHead = i;
  36.         }
  37.         if (depthQueue.isEmpty()) {
  38.             return null;
  39.         }
  40.         return build(0);
  41.     }
  43.     /**
  44.      * 建树
  45.      *
  46.      * @param depth 当前深度
  47.      * @return 该深度结点
  48.      */
  49.     private TreeNode build(int depth) {
  50.         if ((depthQueue.isEmpty()) || (depthQueue.peek() != depth)) {
  51.             return null;
  52.         }
  53.         depthQueue.poll();
  54.         TreeNode root = new TreeNode(numQueue.poll());
  55.         // 左子树优先于右子树
  56.         // 根据题中字符串的性质, 没有左子树一定也没有右子树
  57.         root.left = build(depth + 1);
  58.         root.right = build(depth + 1);
  59.         return root;
  60.     }
  61. }