C++ 6ms clean recursive solution with detailed explanation (with helper - level order traversal from top)


  • 1

    I've seen there are already many posts about this recursive version of solution in the board. I just want to give an explanation and comment about my thinking process.

    My first attempt for tree related problem is always trying to solve it recursively (as naturally derived from the definition of tree data structure). Since we are only given the root node of a tree, it is easier to traverse from top to bottom rather than the other way around, i.e., print node values in level order but from root level to leaf level. Since we are required to print node value from left to right on any given level, so a pre-order traversal with level tracking can easily do the job to save the result (the zero-based vector index perfectly matches the level number). Then we just reverse the result to get the desired answer.
    Btw, this algorithm can be easily extended to arbitrary trees instead of just binary trees.

        // this is the helper function to do level traversal from top to bottom
        void levelOrderTop(TreeNode* r, int level, vector<vector<int>>& res) {
            if (!r) return;
            if (level == res.size()) res.push_back({r->val}); // enter a deeper level for the first time
            else res[level].push_back(r->val); // enter a previously visited level and append node
    
            // do left subtree first since it requires to print from left node at the same level
            levelOrderTop(r->left, level+1,res);
            levelOrderTop(r->right, level+1,res);
        }
        
        vector<vector<int>> levelOrderBottom(TreeNode* r) {
            vector<vector<int>> res;
            levelOrderTop(r, 0, res); // root is at level 0
            reverse(res.begin(), res.end()); // reverse to get order from bottom to root level
            return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.