Is there any better idea than doing regular level order traversal and reverse the result?


  • 81
    S

    The way I see this problem is that it is EXACTLY the same as "Level-Order Traversal I" except that we need to reverse the final container for output, which is trivial. Is there a better idea that fits this problem specifically?

    The attached is my current recursive solution. In each function call, we pass in the current node and its level. If this level does not yet exist in the output container, then we should add a new empty level. Then, we add the current node to the end of the current level, and recursively call the function passing the two children of the current node at the next level. This algorithm is really a DFS, but it saves the level information for each node and produces the same result as BFS would.

    vector<vector<int> > res;
    
    void DFS(TreeNode* root, int level)
    {
        if (root == NULL) return;
        if (level == res.size()) // The level does not exist in output
        {
            res.push_back(vector<int>()); // Create a new level
        }
        
        res[level].push_back(root->val); // Add the current value to its level
        DFS(root->left, level+1); // Go to the next level
        DFS(root->right,level+1);
    }
    
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        DFS(root, 0);
        return vector<vector<int> > (res.rbegin(), res.rend());
    }

  • 16
    I

    Here is my solution. I use queue to do level traversal and then reverse the result.

    class Solution {
    public:
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        vector<vector<int> > levelOrder;
        if(root != NULL) {
            queue<TreeNode *> Q;
            Q.push(root);
            while(!Q.empty()) {
                int n = Q.size();                  // level node count
                vector<int> visit;
                while(n-- > 0) {                   // level traversal 
                    TreeNode *p = Q.front();
                    Q.pop();
                    visit.push_back(p->val);
                    if(p->left) Q.push(p->left);
                    if(p->right) Q.push(p->right);
                }
                levelOrder.push_back(visit);
             }
         }        
        std::reverse(levelOrder.begin(), levelOrder.end());       
        return levelOrder;
        }
    };

  • 0
    R

    I think ItBaker is right, why got cons?


  • 1
    R

    In Java, one easy way is to insert the list into the head of the linkedlist. So at least it is not needed to reverse the list.

    public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<Integer> list= new LinkedList<Integer>();
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        Deque<TreeNode> node_queue=new LinkedList<TreeNode>();
        Deque<Integer> layer_queue=new LinkedList<Integer>();
        
        if (root==null) return result;
        
        list.add(root.val);
        node_queue.addFirst(root);
        layer_queue.addFirst(1);
        
        int current_layer=0;
        
        while(!node_queue.isEmpty()){
            int layer=layer_queue.pollFirst();
            
            if (layer>current_layer){
                List<Integer> temp = new LinkedList<Integer>();
                temp.addAll(list);
                result.add(0,temp);
                list.clear();
                current_layer=layer;
            }
            
            TreeNode node = node_queue.pollFirst();
            
            if (node.left!=null){
                node_queue.addLast(node.left);
                layer_queue.addLast(layer+1);
                list.add(node.left.val);
            }
            if (node.right!=null){
                node_queue.addLast(node.right);
                layer_queue.addLast(layer+1);
                list.add(node.right.val);
            }
        }
        if (list.size()>0) result.add(0,list);
        return result; 
    }
    

    }


  • 0
    S

    Thank you for the solution. However, in the c++ version, the return value is defined as a vector<vector<>>, which does not support push_front() in O(1). If I save the intermediate results in a list, then copy them to the vector, I need to go through even more trouble than using reverse. Then again, I think your solution is very good.


  • 1
    R

    I guess the reason is that @ItBaker still used the {@code: std::reverse()} at the last clause, which is not a 'better' idea.


  • 30
    A
    public class Solution {
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            List<List<Integer>> container = new ArrayList<List<Integer>>();
            if (root == null) return container;
            TreeNode cur = null;
            Queue<TreeNode> sameLevel = new LinkedList<TreeNode>();
            sameLevel.add(root);
            while (!sameLevel.isEmpty()) {
                List<Integer> oneLevel = new ArrayList<Integer>();
                Queue<TreeNode> temp = new LinkedList<TreeNode>();
                while(!sameLevel.isEmpty()) {
                    cur = sameLevel.remove();
                    oneLevel.add(cur.val);
                    if (cur.left != null)  temp.add(cur.left); 
                    if (cur.right != null) temp.add(cur.right);
                }
                container.add(0,oneLevel);
                sameLevel = temp;
            }
            return container;
        }
    }
    

    This is my solution in Java. Since we could just insert element in the head of list, we do not need reverse it in
    the end.


  • 0

    You could also try use a stack instead of a queue to reverse order. I choose this method because in python, list can not be inserted in the front without shifting data. Below is my python implementation.

    def levelOrderBottom(self, root):
        
      if root==None:
        return []
    
      S = []                # a stack
      S.append((root, 0))   # a tuple with a node and its levelcount
    
      i = 0
      while i<len(S):
        cur = S[i]
        if cur[0].right:
          S.append( (cur[0].right, cur[1]+1))      
        if cur[0].left:
          S.append( (cur[0].left, cur[1]+1))
        i+=1
    
      res = []
      curlevel = []
      levelcount = S[len(S)-1][1]
      while S:
        cur = S.pop()
        if cur[1]<levelcount:
          res.append(curlevel)
          curlevel = []
          levelcount = cur[1]
        curlevel.append(cur[0].val)
      res.append(curlevel)
      
      return res

  • 18
    L

    Here is my AC code.
    The idea is very similar to yours. But avoided the reverse of outer vector by calculating tree level first. then pass level down backwards. Root will have the max level

    int findMaxLen(TreeNode* root)
    {
        if(root==NULL) return 0;
        return 1+max(findMaxLen(root->left),findMaxLen(root->right));
    }
    void levelOrderRec(TreeNode* root, vector<vector<int>>& vec, int level)
    {
        if(root==NULL) return;
        vec[level].push_back(root->val);
        levelOrderRec(root->left,vec,level-1);
        levelOrderRec(root->right,vec,level-1);
    }
    
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        vector<vector<int>> result;
        if(root==NULL) return result;
        int count = findMaxLen(root);
        for(int i = 0; i < count; i++)
        {
            vector<int> temp;
            result.push_back(temp);
        }
        levelOrderRec(root, result, count-1);
        return result;
    }
    

  • 2
    T

    Yes, you don't need to reverse the list, but "container.add(0,oneLevel);" takes O(n) to complete. So your solution may take O(n^2) in some corner case - if there is only one node in each level.


  • 1
    Y

    use linkedlist like container, e.g. LinkedList in java which is implemented as a doubled linked list.


  • 0
    Z

    Is vector implemented with re-sizing array in c++? If so, then it is not efficient to insert at front.

    In java, you can either return an ArrayList (re-sizing array) or LinkedList (doubly liked list?) and the latter is efficient supporting insert either end.


  • 0
    Z

    Is there any solution avoiding using a queue? the c++ recursive version op posted was much faster than the version using queues.


  • 0
    Y

    here's my solution with same idea to insert new space before begin(), though, insert() for vector seems to be very inefficient.

    class Solution {
    public:
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
    dfs(root, 0);
    return vec;
    }

    void dfs(TreeNode *node, int dep){
        
        if(!node) return;
            
        if(dep > depth){
            vec.insert(vec.begin(), vector<int>());
            depth++;
        }
            
        if(node->left) dfs(node->left, dep+1);
        
        if(node->right) dfs(node->right, dep+1);
       
        vec[vec.size()-1-dep].push_back(node->val);
        return;
    }
    
    int depth = -1;
    vector<vector<int>> vec;
    

    };


  • 0
    M

    Actually, you could use list in c++, then you can add element in the front.


  • 0
    S

    Yes, but then I'll have to convert the list to vector. It is about the same amount of trouble as reversing a vector.


  • 0
    M

    As I know that you could change the return type from vector<vector<int>> to list<vector<int>>, and submit again. It will still be accepted.


  • 0
    S

    Of course you could, but other parts of the program do not know about this change, and its returned value will still be assigned to vectors, so an implicit conversion needs to take place. It doesn't solve the problem; it just throws the problem somewhere else. Besides, I do not think it is a good practice to secretly modify the interface of a function that has already been agreed upon.


  • -1
    X

    I ran the recursive function twice. For the 1st time, I constructed the empty data structure vector<vector<int> >. For the second time, I filled the numbers in.

    vector<vector<int> > output;
    vector<int> empty;
    int glbLevel = -1;
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        getLevel(root, 0, true);
        getLevel(root, 0, false);
        return output;
    }
    int getLevel(TreeNode *node, int level, bool firstRun){
        int leftLevel, rightLevel;
        if(node == NULL)    return level;
        if(level > glbLevel && firstRun){
            glbLevel = level;
            output.push_back(empty);
        }
        leftLevel = getLevel(node->left, level + 1, firstRun);
        rightLevel = getLevel(node->right, level + 1, firstRun);
        if(!firstRun)   output[glbLevel - level].push_back(node->val);
        return (rightLevel > leftLevel ? rightLevel : leftLevel);
    }
    

  • 1
    F

    Your regular method is THE BEST, complexity of taking the reverse of a vector is ONLY half the length of the vector (calculating the depth at the beginning will cost more, non-recursive way won't save you too much time). Regular solution is simple, neat and efficient.


Log in to reply
 

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