leetcode/1028.cpp at main · h3902340/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <string>
#include <stack>
#include <queue>
using namespace std;

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)
    {
        stack<TreeNode *> waitingStack;
        int depth = 0;
        int val = 0;
        int i = 0;
        while (i < traversal.length())
        {
            while (traversal[i] == '-')
            {
                depth++;
                i++;
            }
            while (isdigit(traversal[i]))
            {
                val = val * 10 + (traversal[i] - '0');
                i++;
            }
            TreeNode *node = new TreeNode();
            node->val = val;
            while (waitingStack.size() != depth)
            {
                waitingStack.pop();
            }
            if (!waitingStack.empty())
            {
                if (waitingStack.top()->left)
                {
                    waitingStack.top()->right = node;
                }
                else
                {
                    waitingStack.top()->left = node;
                }
            }
            waitingStack.push(node);
            depth = 0;
            val = 0;
        }
        while (waitingStack.size() != 1)
        {
            waitingStack.pop();
        }
        return waitingStack.top();
    }
};

string traversal = "1-401--349---90--88";

int main()
{
    Solution sol;
    TreeNode *root = sol.recoverFromPreorder(traversal);
    vector<int> nodes;
    queue<TreeNode *> queue;
    queue.push(root);
    while (!queue.empty())
    {
        TreeNode *node = queue.front();
        queue.pop();
        if (node)
        {
            nodes.push_back(node->val);
            queue.push(node->left);
            queue.push(node->right);
        }
        else
        {
            nodes.push_back(-1);
        }
    }
    int lastNodeVal = nodes[nodes.size() - 1];
    while (lastNodeVal == -1)
    {
        nodes.pop_back();
        lastNodeVal = nodes[nodes.size() - 1];
    }
    printf("[");
    for (int i = 0; i < nodes.size() - 1; i++)
    {
        if (nodes[i] == -1)
        {
            printf("null,");
            continue;
        }
        printf("%d,", nodes[i]);
    }
    printf("%d", nodes[nodes.size() - 1]);
    printf("]\n");

    return 0;
}