从先序遍历还原二叉树

/* 
题目思路：
1. 使用Java流和分割字符串的方法来简化节点的识别和构建。
2. 将输入字符串分割成节点信息。
3. 使用栈来维护当前节点的层级关系，并根据深度信息插入到正确的位置。
*/

import java.util.*;
import java.util.stream.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode recoverFromPreorder(String S) {
        List<String> nodes = Arrays.stream(S.split("(?<=\d)(?=-)|(?<=-)(?=\d)"))
                                    .collect(Collectors.toList());
        Deque<TreeNode> stack = new ArrayDeque<>();
        for (String nodeInfo : nodes) {
            int level = 0;
            while (nodeInfo.charAt(level) == '-') level++;
            int value = Integer.parseInt(nodeInfo.substring(level));
            TreeNode node = new TreeNode(value);
            while (stack.size() > level) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                if (stack.peek().left == null) {
                    stack.peek().left = node;
                } else {
                    stack.peek().right = node;
                }
            }
            stack.push(node);
        }
        while (stack.size() > 1) {
            stack.pop();
        }
        return stack.pop();
    }
}