从先序遍历还原二叉树

解题思路

维护一个list，存放路径节点值。
root为根节点
level表示深度（‘-’的个数）
举例来说，root开始，如果list的大小和level大小相等，说明一直先序遍历还没有到底。直到level的值大小与前一次相等或者变小，说明进行了
回溯，所以要更新list的值。

代码

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode recoverFromPreorder(String S) {
        ArrayList<TreeNode> alst = new ArrayList<TreeNode>();
        int pos = 0;
        int level =0;
        String value = "";
        TreeNode root = new TreeNode(level);
        int lastlevel = 0;
        while(pos<S.length()){
            level = 0;
            while(pos<S.length() && S.charAt(pos)=='-'){
                level ++;
                pos++;
            }
            int c = pos;
            while(pos<S.length() && S.charAt(pos)!='-'){
                pos++;
            }
            TreeNode n = new TreeNode(Integer.valueOf(String.valueOf(S.substring(c,pos))));
            if(alst.size()==0){
                root = n;
                alst.add(n);
            }else{
                if(alst.size()==level){
                	
                    alst.get(level-1).left = n;
                    alst.add(n);
                }else{
                	if(lastlevel > level) {
                        alst.get(level-1).right = n;
                        alst.set(level, n);
                        while(alst.size()>level+1) {
                        	alst.remove(alst.size()-1);
                        }
                	}else {
                        alst.get(level-1).right = n;
                        alst.set(level, n);
                	}


                }
            }
            lastlevel = level;
        }
        return root;
        
        }
    }