LeetCode/BinaryTreeLevelOrderTraversalII.cpp at master · Riddance/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
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        queue<TreeNode *> walk_queue;
        vector<vector<int> > results;
        vector<int> result;

        if (!root)
            return results;
        else
            walk_queue.push(root);

        walk_queue.push(NULL);

        while (!walk_queue.empty()) {
            TreeNode *temp = walk_queue.front();
            walk_queue.pop();

            if (!temp && !result.empty()) {
                results.insert(results.begin(), result);
                result.clear();
                continue;
            }

            result.push_back(temp->val);

            if (temp->left)
                walk_queue.push(temp->left);

            if (temp->right)
                walk_queue.push(temp->right);

            if (walk_queue.size() > 1 && !(walk_queue.front()))
                walk_queue.push(NULL);
        }

        return results;
    }
};