Using Simple DFS


  • 0
    F

    The basic idea is to first find the depth of the tree using dfs. The variable count is used to indicate the current level. Once the level is found , create a vector of the size maximum level (here its variable max).

    Then traverse again, this time additionally store the values in the vector. Note here we can directly give the index for insertion. For a normal level order traversal, we have to use index i instead of max-i-1 .

    class Solution
    {
    public: int max=0;
            void dfs(TreeNode *root,int i,vector<vector<int>> &lst)
            {
                lst[max-i-1].push_back(root->val);   // push back at max-current level
                
                if(root->left!=NULL)
                 dfs(root->left,i+1,lst);
                if(root->right!=NULL)
                 dfs(root->right,i+1,lst);
            
            }
            void dfs2(TreeNode *root,int i)   // find the maximum level
            {
                 if(max<i) max=i;
                 
                if(root->left!=NULL)
                 dfs2(root->left,i+1);
                if(root->right!=NULL)
                 dfs2(root->right,i+1);
            
            }
        vector<vector<int>> levelOrderBottom(TreeNode *root)
        {  
            vector<vector<int>> lst;
            if(root==NULL) return lst;
            
            dfs2(root,1);
           lst.resize(max);
            dfs(root,0,lst);
            return lst;
        }
    };

  • 0
    S

    Pay attention to "Writing code? Select all code block then click on the {} button to preserve code formatting.” above text editor.


  • 0
    F

    Thanx...done that


Log in to reply
 

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