Is there a better solution?


  • 4
    C

    I use a queue to iterate the tree, and a label named head to point to the first node of each level.
    Nevertheless, I don't think the code is concise enough. Is there a better solution for this question?

    public class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> ret = new ArrayList<List<Integer>>();
            if(root==null) return ret;
            TreeNode head = root;
            Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
            queue.offer(root);
            List<Integer> level = null;
            boolean headFound = false;
            while(!queue.isEmpty())
            {
                TreeNode top = queue.poll();
                if(top==head)
                {
                    ret.add(level);
                    level = new ArrayList<Integer>();
                    headFound = false;
                }
                if(top.left!=null) queue.offer(top.left);
                if(top.right!=null) queue.offer(top.right);
                level.add(top.val);
                if(!headFound && (top.left!=null || top.right!=null))
                {
                    headFound = true;
                    if(top.left!=null) head = top.left;
                    else head = top.right;
                }
            }
            ret.add(level);
            ret.remove(0);
            return ret;
        }
    }

  • 8
    S

    By better if you mean elegant,then may be :/

    class Solution {
    public:
        vector<vector<int> > levelOrder(TreeNode *root) {
            struct queue<TreeNode *>q;
            struct TreeNode *temp=root;
            vector<vector<int> > v1;
            vector<int> v;
            if(!root)                                            //if root is NULL return vector of vectors
            return v1;                                              
            q.push(temp);                                        //we don't want an empty queue,do we?
            long long ago;      //in a galaxy far far away
            ago=0;
            while(!q.empty())
            {  
                ago=q.size();                                 //this is the tricky part done so that every thing gets pushed and popped 
                while(ago)                                    //our hero comes to play
                {temp=q.front();                                //but ofcourse if tree is 1,#2,3 (let) then 2 should be printedfirst(root)
                v.push_back(temp->val);                         //I wonder why they took vector of vectors,that explains less accuracy.
                if(temp->left)
                q.push(temp->left);                             //go left for the 1 ,mind you this is iterative, queue =2,1,
                if(temp->right)
                q.push(temp->right);                            //go right                queue2,1,3
                q.pop();                                        //pop 2,queue=1,3 count=0 go up count 1 again!! ,queue front has 2(FIFO)
                ago--;
                }
                v1.push_back(v);                                //vector of vectors :(
                v.clear();                                     // but ofcourse we don't need extra memory
            }
            
            return v1;                                        //vector of vectors :(. 
        }
    };
    
    
                                                             //Much love to Shangrila for closing questions /answers without explanation   
    

  • 0
    C

    My solution is as below. I also use a queue to iterate the tree. The main idea is that we can keep two pointers which point to the end of current level (curLevelEnd) and the end of the next level (nextLevelEnd) respectively. When we add a TreeNode to the queue, we just update nextLevelEnd to point to this node. When we reach the end of current level, nextLevelEnd is assigned to curLevelEnd.

    vector<vector<int> > levelOrder(TreeNode *root) {
        vector<vector<int>> result;
        if (!root) return result;
        queue<TreeNode*> q;
        q.push(root);
        result.push_back(vector<int>());
        TreeNode* curLevelEnd = root, *nextLevelEnd = NULL;
        while (!q.empty())
        {
            TreeNode* tmp = q.front();
            q.pop();
            result[result.size() - 1].push_back(tmp->val);
            if (tmp->left)
            {
                q.push(tmp->left);
                nextLevelEnd = tmp->left;
            }
            if (tmp->right)
            {
                q.push(tmp->right);
                nextLevelEnd = tmp->right;
            }
            if (tmp == curLevelEnd)
            {
                result.push_back(vector<int>());
                curLevelEnd = nextLevelEnd;
            }
        }
        if (result[result.size() - 1].size() == 0) result.pop_back();
        return result;
    }

  • 0
    R

    My answer is similar to @cjxxm. It is written in java.

    public class Solution {
    public List<List<Integer>> levelOrder(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(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(list);
        return result;
    }
    

    }


  • 42
    D

    Maybe just a little bit less code in java:

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        List<TreeNode> level = new ArrayList<>();
        level.add(root);
        while(true){
            if (level.isEmpty() || level.get(0) == null){
                break;
            }
            List<TreeNode> nextLevel = new ArrayList<>();
            List<Integer> currentLevel = new ArrayList<>();
    
            for (TreeNode node : level){
                currentLevel.add(node.val);
                if (node.left != null) nextLevel.add(node.left);
                if (node.right != null) nextLevel.add(node.right);
            }
            result.add(currentLevel);
            level = nextLevel;
        }
        return result;
    }

  • 4
    Y
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        if(root==null)  
            return result;
        List<TreeNode> cur=new ArrayList<TreeNode>();
        cur.add(root);
        while(cur.size()!=0){
            List<Integer> toAdd=new ArrayList<Integer>();
            List<TreeNode> next=new ArrayList<TreeNode>();
            for(TreeNode i:cur){
                toAdd.add(i.val);
                if(i.left!=null)
                    next.add(i.left);
                if(i.right!=null)
                    next.add(i.right);
            }
            result.add(toAdd);
            cur=next;
        }
        return result;
    }
    

  • 0
    Y

    This is my iterative solution


  • 0
    C

    I use the null as the split between levels, here's my

    public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        List<Integer> tmp;
        TreeNode cur;
        if (root == null) {
            return ret;
        }
        queue.add(root);
        queue.add(null);
        while (!queue.isEmpty()) {
            tmp = new ArrayList<Integer>();
            for (cur = queue.remove(); cur != null; cur = queue.remove()) {
                tmp.add(cur.val);
                if (cur.left != null) queue.add(cur.left);
                if (cur.right != null) queue.add(cur.right);
            }
            if (tmp.size() > 0) {
                queue.add(null);
                ret.add(tmp);
            }
        }
        return ret;
    }
    }

  • 0

    thank you. very nice and organized code.


  • 0
    B

    That's super clear solution without using queue. Thx so much!
    I'm just thinking maybe we can add "if(root == null) return res;" into the second line. And also change the while into "while(!level.isEmpty())", which is a little bit clear and easy to understand.


  • 0
    N
    This post is deleted!

  • 0
    N

    Here is my recursive solution:

    class Solution:
        # @param root, a tree node
        # @return a list of lists of integers
        def levelOrder(self, root):
            if (root == None):
                return [];
            else:
                all_levels = [[root.val]]
                left_levels = self.levelOrder(root.left)
                right_levels = self.levelOrder(root.right)
                m = min(len(left_levels), len(right_levels))
                for i in range(m):
                    all_levels.append( left_levels[i] + right_levels[i])
                if (len(left_levels)>m):
                    for j in range(m, len(left_levels)):
                        all_levels.append(left_levels[j])
            
                if (len(right_levels)>m):
                    for k in range(m, len(right_levels)):
                        all_levels.append(right_levels[k])
                return all_levels
    

  • 1

    I also use the NULL as the split between levels, here's my:

    class Solution {
    public:
        std::vector<std::vector<int> > levelOrder(TreeNode *root) {
            std::vector<std::vector<int> > result;
    		if (root == NULL)
    			return result;
    		std::deque<TreeNode *> wait_nodes;
    		wait_nodes.push_back(root);
    		wait_nodes.push_back(NULL);
    		std::vector<int> nodes_val;
    		while (wait_nodes.size() != 1) {
    			root = wait_nodes.front();
    			wait_nodes.pop_front();
    			while (root != NULL) {
    				nodes_val.push_back(root->val);
    				if (root->left != NULL)
    					wait_nodes.push_back(root->left);
    				if (root->right != NULL)
    					wait_nodes.push_back(root->right);
    				root = wait_nodes.front();
    				wait_nodes.pop_front();
    			}
    			result.push_back(nodes_val);
    			wait_nodes.push_back(NULL);
    			nodes_val.clear();
    		}
    		return result;
        }
    };

  • 0
    L

    Nothing new here, just a bit simpler.

    class Solution {
    public:
        vector<vector<int> > levelOrder(TreeNode *root) {            
            vector<vector<int> > res;            
            vector<TreeNode*> level(root != 0, root);
            
            int i = 0, l = 0;
            
            while(i < level.size()){
                
                res.push_back( vector<int>() );
                
                for(int n = level.size(); i < n; i++){
                    res[l].push_back( level[i]->val );
                    
                    if( level[i]->left )
                        level.push_back( level[i]->left );
                    
                    if( level[i]->right )
                        level.push_back( level[i]->right );    
                }                
                l++;
            }            
            return res;
        }
    };

  • 0
    M

    wow! what a neat solution! Up stair's advice is great too.


  • 0
    Q
    This post is deleted!

  • 0
    R

    a very naive BFS using two queues,one for every level and one for the whole loop.

    class solution{public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q,l;
        vector<vector<int>> ans;
        if (root == NULL) return ans;
        q.push(root);
        l.push(root);
        while (!q.empty())
        {
            vector<int> tmp;
            while (!l.empty())
            {
                TreeNode* t = l.front();
                l.pop();
                q.pop();
                tmp.push_back(t->val);
                if (t->left != NULL)
                    q.push(t->left);
                if (t->right != NULL)
                    q.push(t->right);
            }
            ans.push_back(tmp);
            tmp.clear();
            l = q;
        }
        return ans;
    }}

Log in to reply
 

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