Q1028

https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/discuss/274621/JavaC%2B%2BPython-Iterative-Stack-Solution

import java.util.*;

public class Q1028 {
    public static void main(String[] args) {

    }
    public TreeNode recoverFromPreorder(String S) {
        int depth, val;
        Stack<TreeNode> stack = new Stack<>();
        for (int i = 0; i < S.length();) {
            for (depth = 0; S.charAt(i) == ‘-‘; i++) {
                depth++;
            }
            for (val = 0; i < S.length() && S.charAt(i) != ‘-‘; i++) {
                val = val * 10 + (S.charAt(i) - ‘0‘);
            }
            while (stack.size() > depth) { // 此时肯定是一个分支深度遍历完了，从另外一个分支开始遍历
                stack.pop();
            }
            TreeNode node = new TreeNode(val);
            if (!stack.isEmpty()) {
                if (stack.peek().left == null) {
                    stack.peek().left = node;
                } else {
                    stack.peek().right = node;
                }
            }
            stack.add(node);
        }
        while (stack.size() > 1) {
            stack.pop();
        }
        return stack.pop();
    }
}

weak first question

原文：https://www.cnblogs.com/memo20/p/13155863.html