Binary Tree Level Order Traversal Algorithm

The Binary Tree Level Order Traversal II algorithm is a modification of the traditional level order traversal algorithm for binary trees. It is designed to return the node values of a given binary tree in level order, but with a twist - the values are returned in a bottom-up fashion, meaning the nodes at the lowest level of the tree are returned first, followed by the nodes at the second-lowest level, and so on, until the root node is returned last. This algorithm is particularly useful for problems that require processing the nodes of a binary tree in a specific order, such as constructing a new tree or determining if two trees are mirror images of one another. To implement the Binary Tree Level Order Traversal II algorithm, a popular method is to use a breadth-first search (BFS) approach, typically with a queue data structure. The algorithm starts by enqueuing the root node of the binary tree. Then, while the queue is not empty, it dequeues the front node, processes its value (usually by appending it to a list), and then enqueues its children (if any) in left-to-right order. This process is repeated for each node in the queue until all nodes have been processed. Once the traversal is complete, the algorithm reverses the list of values to obtain the desired bottom-up order. Another approach is to use a depth-first search (DFS) algorithm, which involves a recursive traversal of the tree, keeping track of the current level of each node, and appending the node values to a list (or lists) in the corresponding level. Once the traversal is complete, the lists of values for each level are combined in reverse order to obtain the final bottom-up list of values.
/**
 * 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> > levelOrder(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        vector<vector<int>> result;
        if (root == NULL) return result;
        
        queue<TreeNode*> nodeQueue;
        vector<int> value;
        nodeQueue.push(root);
        int nodeNow = 1;
        int nodeNext = 0;
        
        while (!nodeQueue.empty()) {
            TreeNode *node = nodeQueue.front();
            nodeQueue.pop();
            nodeNow -= 1;
            value.push_back(node->val);
            if (node->left) {
                nodeQueue.push(node->left);
                nodeNext += 1;
            }
            if (node->right) {
                nodeQueue.push(node->right);
                nodeNext += 1;
            }
            if (nodeNow == 0) {
                result.push_back(value);
                value.clear();
                nodeNow = nodeNext;
                nodeNext = 0;
            }
        }
        return move(result);
    }
};

LANGUAGE:

DARK MODE: