My AC Java code


  • 13
    L

    I use two stacks, one for processing current layer and one for storing nodes for the next layer. I also use a flag (order in your code) to indicate the direction. It is straightforward

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> output = new ArrayList<List<Integer>>();
        if (root == null) return output;
        Stack<TreeNode> cur_layer = new Stack<TreeNode>(); cur_layer.push(root);
        Stack<TreeNode> next_layer = new Stack<TreeNode>();
        List<Integer> layer_output = new ArrayList<Integer>();
        int d = 0; // 0: left to right; 1: right to left.
        
        while (!cur_layer.isEmpty()){
        	TreeNode node = cur_layer.pop();
        	layer_output.add(node.val);
        	if(d==0){
        		if (node.left != null) next_layer.push(node.left);
        		if (node.right != null) next_layer.push(node.right);
        	}else{
        		if (node.right != null) next_layer.push(node.right);
        		if (node.left != null) next_layer.push(node.left);
        	}
        	
        	if (cur_layer.isEmpty()){
        		output.add(layer_output);
        		layer_output = new ArrayList<Integer>();
        		cur_layer = next_layer;
        		next_layer = new Stack<TreeNode>();;
        		d ^= 1;
        	}
        }
        return output;
    }

  • 0
    L

    You can use output size to figure out d, Actually, d = output.size() % 2, so one less thing to wrong about.


  • 1

    Steps for solution:

    Create an empty stack s and push root to it.

    while stack is not NULL Do following:-

    • Create a empty stack called tempStack.

    • Pop a node from stack and push it to tempStack depending on directionFlag.

    • Change directionFlag to change the direction of traversal.

    • set stack=tempStack.

      public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            
            List<List<Integer>> result=new ArrayList<List<Integer>>();
            Stack<TreeNode> stack=new Stack<TreeNode>(); 
            
             if(root==null) return result;
             
            stack.push(root);  
              
            boolean directionflag=false;  
            while(!stack.isEmpty())  
            {  
                List<Integer> arr = new ArrayList<>();
                Stack<TreeNode> tempStack=new Stack<TreeNode>();  
              
                while(!stack.isEmpty())  
                {  
                    
                    TreeNode tempNode=stack.pop();
                    arr.add(tempNode.val);
                 
                    if(!directionflag)   
                    {  
                        if(tempNode.left!=null)   
                         tempStack.push(tempNode.left);  
                        if(tempNode.right!=null)   
                         tempStack.push(tempNode.right);
                         
                        
                    }else  
                    {  
                        if(tempNode.right!=null)   
                         tempStack.push(tempNode.right);  
                        if(tempNode.left!=null)   
                         tempStack.push(tempNode.left);  
                    }
                     
                }  
                // for changing direction  
                directionflag=!directionflag;  
                stack=tempStack; 
                
               result.add(arr);
            }  
        return result;
    
        }

Log in to reply
 

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