Saturday, August 15, 2015

LeetCode OJ - Binary Tree Level Order Traversal II

Problem:

Please find the problem here.

Solution:

Just reverse the output from the solution I had for Binary Tree Level Order Traversal. The code is almost literally identical.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

#include "LEET_BINARY_TREE_LEVEL_ORDER_TRAVERSAL_II.h"

#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>

using namespace std;

namespace _LEET_BINARY_TREE_LEVEL_ORDER_TRAVERSAL_II
{
    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)
        {
            vector<vector<int> > result;


            vector<TreeNode*> list1;
            vector<TreeNode*> list2;

            vector<TreeNode*>& this_layer = list1;
            vector<TreeNode*>& next_layer = list2;

            if (root != NULL)
            {
                this_layer.push_back(root);
            }

            while (this_layer.size() != 0)
            {
                vector<int> this_layer_values;
                for (unsigned int i = 0; i < this_layer.size(); i++)
                {
                    this_layer_values.push_back(this_layer[i]->val);
                    TreeNode* left_child = this_layer[i]->left;
                    if (left_child != NULL)
                    {
                        next_layer.push_back(left_child);
                    }
                    TreeNode* right_child = this_layer[i]->right;
                    if (right_child != NULL)
                    {
                        next_layer.push_back(right_child);
                    }
                }

                this_layer.clear();
                swap(this_layer, next_layer);
                result.push_back(this_layer_values);
            }

            reverse(result.begin(), result.end());
            return result;
        }
    };
}

using namespace _LEET_BINARY_TREE_LEVEL_ORDER_TRAVERSAL_II;

int LEET_BINARY_TREE_LEVEL_ORDER_TRAVERSAL_II()
{
    TreeNode a(3);
    TreeNode b(9);
    TreeNode c(20);
    TreeNode d(15);
    TreeNode e(7);

    a.left = &b;
    a.right = &c;
    b.left = NULL;
    b.right = NULL;
    c.left = &d;
    c.right = &e;
    d.left = NULL;
    d.right = NULL;
    e.left = NULL;
    e.right = NULL;

    Solution solution;
    vector<vector<int> > result = solution.levelOrderBottom(&a);
    for (unsigned int i = 0; i < result.size(); i++)
    {
        for (unsigned int j = 0; j < result[i].size(); j++)
        {
            cout << result[i][j] << " ";
        }

        cout << endl;
    }
    return 0;
}

No comments :

Post a Comment