107. Binary Tree Level Order Traversal II

2020, Nov 17 One min read

1. Description

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

2. Solutions

Breadth-First Search

n is the number of nodes in i_root
Time complexity: O(n)
Space complexity: O(n)

class Solution
{
public:
    // vector<vector<int>> levelOrderBottom(TreeNode* root)
    vector<vector<int>> levelOrderBottom(const TreeNode *i_root)
    {
        if(!i_root) return vector<vector<int>>{};

        vector<vector<int>> result;
        queue<const TreeNode *> currentLevelNodes{{i_root}};
        queue<const TreeNode *> nextLevelNodes;

        vector<int> levelNodesValue;
        while(!currentLevelNodes.empty() || !nextLevelNodes.empty())
        {
            if(currentLevelNodes.empty())
            {
                result.push_back(levelNodesValue);
                levelNodesValue.clear();

                swap(currentLevelNodes, nextLevelNodes);
            }
            else
            {
                auto node = currentLevelNodes.front();
                currentLevelNodes.pop();

                levelNodesValue.push_back(node->val);

                if(node->left) nextLevelNodes.push(node->left);
                if(node->right) nextLevelNodes.push(node->right);
            }
        }

        result.push_back(levelNodesValue);
        reverse(result.begin(), result.end());

        return result;
    }
};