Binary Tree Level Order Traversal II

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).

For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7

return its bottom-up level order traversal as: [ [15,7], [9,20], [3] ]

Solution: Reverse Level order traversal

We can use recursive method to find out the level order traversal, then reverse the order.

    void levelOrderBottomUtil(TreeNode* root, int depth, vector<vector<int>> &ans) {
        if (!root) return;

        if (ans.size() == depth) ans.push_back({});
        if (root->left) levelOrderBottomUtil(root->left, depth+1, ans);
        if (root->right) levelOrderBottomUtil(root->right, depth+1, ans);
        ans[depth].push_back(root->val);
    }

    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;
        levelOrderBottomUtil(root, 0, ans);
        reverse(ans.begin(), ans.end());
        return ans;
    }

Solution: Count the nodes at current level.

We count the nodes at current level. And for every node, we enqueue its children to queue.

vector<vector<int>> levelOrder(TreeNode* root) {
    if (!root) return {};

    queue<TreeNode *> q;
    vector<vector<int>> ans;
    q.push(root);

    while (true) {
        int nodeCount = q.size();
        if (nodeCount == 0) break;

        ans.push_back({});
        while (nodeCount > 0) {
            TreeNode *node = q.front();
            ans.back().push_back(node->val);
            q.pop();

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

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