AC BFS Java code, no recursive.


  • 0

    My thinking is similar to Level order traversal, but adjust the add order and traversal order alternatively.
    Below is the code for your info:

     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
     
        List<List<Integer>> res = new ArrayList<List<Integer>> ();
        ArrayList<TreeNode> list =  new ArrayList<TreeNode>();
        
    	if(null == root){
    		return res;
    	}
    	
    	int count=0;
    	list.add(root);
    	
    	while (!list.isEmpty()) {
    		ArrayList<TreeNode> nextlist = new ArrayList<TreeNode>();
    		ArrayList<Integer> intlist = new ArrayList<Integer>();
    		TreeNode tn;
    
    		for (int i = list.size() - 1; i >= 0; i--) {
    			tn = list.get(i);
    			intlist.add(tn.val);
    			if (1 == count % 2) {
    				if (null != tn.right)
    					nextlist.add(tn.right);
    				if (null != tn.left)
    					nextlist.add(tn.left);
    			} else {
    				if (null != tn.left)
    					nextlist.add(tn.left);
    				if (null != tn.right)
    					nextlist.add(tn.right);
    			}
    		}
    
    		res.add(intlist);
    		list = nextlist;
    		count++;
    	}
       
    	return res;
       
    }

Log in to reply
 

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