Java Iteratively(BFS) and Recursively(DFS) beat 95%


  • 2

    Usually operations on Binary Tree can be done both Iteratively(BFS) and Recursively(DFS).

    In this case, Iteratively traverse would be simple and clear with Stack.

    Reverse odd index row before return.

    public class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) 
        {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            if(root == null) return res;
            
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            q.add(root);
            
            int cur = 1;
            int total = 0;
            TreeNode temp = null;
            List<Integer> tempList = new ArrayList<Integer>();
            
            
            while(!q.isEmpty())
            {
                
                temp = q.poll();
                cur--;
                tempList.add(temp.val);
                if(temp.left != null)
                {
                    q.add(temp.left);
                    total++;
                }
                if(temp.right != null)
                {
                    q.add(temp.right);
                    total++;
                }
                if(cur == 0)
                {
                    cur = total;
                    total = 0;
                    
                    res.add(new ArrayList<Integer>(tempList));
                    tempList = new ArrayList<Integer>();
                }
            }
            
            for(int i = 1; i < res.size();i+=2)
            {
                Collections.reverse(res.get(i));
            }
            
            return res;
        }
    }
    

    Recursively:

    The key is to remember which level / line / row / floor the current node belongs to, for adding.
    pre-order or in-order wont hurt, since node will be added to different level.

    public class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) 
        {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            if(root == null) return res;
            
            helper(res,root,0);
            
            for(int i = 1; i < res.size();i+=2)
            {
                Collections.reverse(res.get(i));
            }
            
            return res;
        }
        
        
        public void helper(List<List<Integer>> res, TreeNode root, int level)
        {
            if(root == null) return;
            
            List<Integer> tempList = new ArrayList<Integer>();
            if(level > res.size()-1) res.add(new ArrayList<Integer>());
            
            res.get(level).add(root.val);
            
            helper(res,root.left,level+1);
            helper(res,root.right,level+1);
        }
    }
    

    Recursive solution beat 95%, better than Iterative solution. I guess the main reason is I did sh*ty code with Iterative solution.


Log in to reply
 

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