/**
 * 二元樹節點的定義。
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* recoverFromPreorder(string traversal) {
        // 找出第一個連字符的位置，它表示深度
        auto firstDashIdx = traversal.find('-');

        // 如果沒有連字符，則表示這是個單一節點的樹
        if (firstDashIdx == string::npos) 
            return new TreeNode(stoi(traversal));

        // 使用第一個連字符之前的子字串來創建根節點
        TreeNode* root = new TreeNode(stoi(traversal.substr(0, firstDashIdx)));

        // 使用堆疊來跟踪每個深度的樹節點
        stack<TreeNode*> treeStack;
        treeStack.push(root);

        // 遍歷整個輸入字符串
        for (int i = firstDashIdx; i < traversal.size(); i++) {
            int depthCount = 0;

            // 計算連續連字符的數量以確定深度
            while (i < traversal.size() && traversal[i] == '-') {
                depthCount++;
                i++;
            }

            // 從堆疊中彈出節點直到堆疊大小與當前深度相符
            while (treeStack.size() > depthCount) 
                treeStack.pop();

            // 找到下一個連字符或字符串結尾以獲取當前節點的值
            auto nextDashIdx = traversal.find('-', i);
            TreeNode* currentNode;

            if (nextDashIdx == string::npos) {
                // 如果沒有更多連字符，這是路徑中的最後一個節點
                currentNode = new TreeNode(stoi(traversal.substr(i)));
                i = traversal.size(); // 移動到字符串的末尾
            } else {
                // 提取當前位置和下一個連字符之間的節點值
                currentNode = new TreeNode(stoi(traversal.substr(i, nextDashIdx - i)));
                i = nextDashIdx - 1; // 將索引更新到下一個連字符之前
            }

            // 確定當前節點應該作為左子節點還是右子節點
            if (treeStack.top()->left == nullptr) {
                // 如果沒有左子節點，將當前節點分配為左節點
                treeStack.top()->left = currentNode;
            } else {
                // 否則，將當前節點分配為右節點
                treeStack.top()->right = currentNode;
            }

            // 將當前節點推入堆疊
            treeStack.push(currentNode);
        }

        // 返回重建的二元樹的根節點
        return root;
    }
};

class TreeNode:
    def __init__(self, x, left=None, right=None):
        self.val = x
        self.left = left
        self.right = right

class Solution:
    def recoverFromPreorder(self, traversal: str) -> TreeNode:
        # 找到第一個短線的位置，以指示深度
        firstDashIdx = traversal.find('-')

        # 如果沒有短線，則是單一節點的樹
        if firstDashIdx == -1:
            return TreeNode(int(traversal))

        # 使用第一個短線之前的子字串建立根節點
        root = TreeNode(int(traversal[:firstDashIdx]))

        # 使用堆疊記錄每個深度的樹節點
        treeStack = [root]

        # 遍歷剩餘的遍歷字串
        i = firstDashIdx
        while i < len(traversal):
            depthCount = 0

            # 計數連續的短線以確定深度
            while i < len(traversal) and traversal[i] == '-':
                depthCount += 1
                i += 1

            # 從堆疊中彈出節點，直到大小符合當前深度
            while len(treeStack) > depthCount:
                treeStack.pop()

            # 找到下一個短線或字串結尾以獲取當前節點的值
            nextDashIdx = traversal.find('-', i)
            if nextDashIdx == -1:
                # 如果沒有更多短線，則是路徑中的最後一個節點
                currentNode = TreeNode(int(traversal[i:]))
                i = len(traversal)  # 移動到字串的結尾
            else:
                # 提取當前位置和下一個短線之間的節點值
                currentNode = TreeNode(int(traversal[i:nextDashIdx]))
                i = nextDashIdx - 1  # 更新索引至緊鄰的下一個短線之前

            # 檢查當前節點應為左子或右子
            if treeStack[-1].left is None:
                # 如果沒有左子，則將當前節點分配給左子
                treeStack[-1].left = currentNode
            else:
                # 否則，將當前節點分配給右子
                treeStack[-1].right = currentNode

            # 將當前節點推入堆疊
            treeStack.append(currentNode)

        # 返回重建後二元樹的根
        return root