Java iteration with Deque


  • 0
    U

    Why use iteration? avoid the stack overflow in case we have a giant binary tree
    why deque ? cuz we can either start from the tail or head based on our approach on certian levels

    class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<>();
            if (root == null) {
                return res;
            }
            Deque<TreeNode> dq = new LinkedList<>();
            dq.offerFirst(root);
            boolean flag = true;
            while(!dq.isEmpty()) {
                int size = dq.size();
                List<Integer> level = new ArrayList<>();
                if(flag) {
                    for(int i = 0 ; i < size ; i ++) {
                        TreeNode temp = dq.pollFirst();
                        if(temp.left != null) {
                            dq.offerLast(temp.left);
                        }
                        if(temp.right != null) {
                            dq.offerLast(temp.right);
                        }
                        level.add(temp.val);
                    }
                }else {
                    for(int i =  0 ; i < size ; i ++) {
                        TreeNode temp = dq.pollLast();
                        if(temp.right != null) {
                            dq.offerFirst(temp.right);
                        }
                        if(temp.left != null) {
                            dq.offerFirst(temp.left);
                        }
                        level.add(temp.val);
                    }
                    
                }
                        res.add( new ArrayList<>(level));
                        flag = !flag;
            }
                        return res;
        }
    }
    
    

  • 0
    L

    '''
    struct TreeNode zigzagLevelOrder(struct TreeNode* root) {
    struct TreeNode *temp;
    int RtoL = 1;
    struct Queue Q;
    if(!root) return 0;
    Q=CreateQueue();
    Enqueue(Q,root);
    While(!IsEmptyQueue(Q))
    {
    temp = Dequeue(Q);
    Printf("%d", temp->data);
    if(RtoL==1)
    {
    if(temp->right) Enqueue(Q,temp->right);
    if(temp->left) Enqueue(Q,temp->left);
    RtoL=0;

        }
        else
             {
           
            if(temp->left) Enqueue(Q,temp->left);
            if(temp->right) Enqueue(Q,temp->right);
            RtoL=1;
            
        }
            
        
    }
    

    }
    '''


  • 0
    N

    ....
    class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<TreeNode>();
    List<List<Integer>> levelList = new ArrayList();
    List<Integer> list ;
    if(root == null)
    return levelList;
    q.add(root);
    int level = 0;
    int nodecount;
    while(!q.isEmpty()){
    nodecount = q.size();
    list = new ArrayList();
    for(int i=0;i<nodecount;i++){
    TreeNode node = q.remove();
    if(level%2 == 0)
    list.add(node.val);
    else
    list.add(0,node.val);
    if(node.left != null)
    q.add(node.left);
    if(node.right != null)
    q.add(node.right);

        }
            levelList.add(list);    
            level++;
        }
        
        return levelList;     
        
    }
    

    }
    ....


Log in to reply
 

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