题目

我们从二叉树的根节点 root 开始进行深度优先搜索。 在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。 如果节点只有一个子节点，那么保证该子节点为左子节点。 给出遍历输出 S，还原树并返回其根节点 root。

思路

先序遍历为根，左，右。 记当前节点为 T T T，上一个节点为 S S S，那么实际上只有两种情况： T T T 是 S S S 的左子节点； T T T 是根节点到 S S S 这一条路径上（不包括 S S S）某一个节点的右子节点。 由于先序遍历的性质，且 T T T 是紧挨 S S S 的后一个，所以 T T T 不可能是 S S S 的右子节点，所以 T T T 只有可能是 S S S 的祖辈节点的右子节点 在遍历字符串，确定节点深度和数值的同时维护一个栈，用来存储等待构建子树的父节点。由于先序遍历的先左后右，当节点入栈时，栈的size可代表下一层节点的level。如果当前节点的level == size，则将peek.left = cur_node ，否则出栈元素，直到栈的size==level（由于后续字符串遍历到的节点为当前节点兄弟节点，或者当前节点祖辈的兄弟节点，所以 size>level），peek.right = cur_node。最后，当前节点也入栈，等待后续节点构建它的子树。

class Solution {
          
   
    public TreeNode recoverFromPreorder(String S) {
          
   
    	//LinkedList 作为栈
        Deque<TreeNode>deque = new LinkedList<>();
        //level从0开始，代表第一层
        int level = 0;
        int pos = 0;
        while(pos < S.length()){
          
   
            if(S.charAt(pos) != -){
          
   
                int []res = getNum(S,pos);
                int val = res[0];
                pos = res[1];
                TreeNode node = new TreeNode(val);
               	//因为level从0开始，所以正好当level==size时，
                //代表栈顶元素为当前节点的父节点
                if(level == deque.size()){
          
   
                    if(!deque.isEmpty())
                        deque.peek().left = node;
                }else{
          
   
                	//去除大于等于当前节点深度的栈中的节点
                	//类似先序的回溯过程
                    while(deque.size() > level){
          
   
                        deque.pop();
                    }
                    deque.peek().right = node;
                }
                deque.push(node);
                level = 0;
            }else{
          
   
                level++;
                pos++;
            }
        }
        while(deque.size() > 1){
          
   
            deque.pop();
        }
        return deque.peek();
    }
    int[] getNum(String s,int pos){
          
   
        int end = pos;
        while(end < s.length()&&s.charAt(end) != -){
          
   
            end++;
        }
        return new int[]{
          
   Integer.valueOf(s.substring(pos,end)),end};
    }
}