LeetCode - Medium - 103. Binary Tree Zigzag Level Order Traversal

- 日理万妓 2022-10-06 12:50 23阅读 0赞

## Topic ##

*  Stack
 *  Tree
 *  Breath-first Search

## Description ##

[https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/][https_leetcode.com_problems_binary-tree-zigzag-level-order-traversal]

Given the `root` of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).

**Example 1:**  
![788a88ab78ebe886286d553023e6c9c9.png][]

Input: root = [3,9,20,null,null,15,7]
    Output: [[3],[20,9],[15,7]]

**Example 2:**

Input: root = [1]
    Output: [[1]]

**Example 3:**

Input: root = []
    Output: []

**Constraints:**

*  The number of nodes in the tree is in the range `[0, 2000]`.
 *  `-100 <= Node.val <= 100`

## Analysis ##

方法一：DFS

方法二：BFS

## Submission ##

import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class BinaryTreeZigzagLevelOrderTraversal { 
    	
    	//方法一：DFS
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) { 
        	List<List<Integer>> result = new ArrayList<>();
        	zigzagLevelOrder(root, 0, result);
            return result;
        }
        
        private void zigzagLevelOrder(TreeNode node, int level, List<List<Integer>> result) { 
        	if(node == null) return;
        	
    		if(level == result.size()) { 
    			List<Integer> temp = new LinkedList<>();
    			temp.add(node.val);
    			result.add(temp);
    		}else { 
    			List<Integer> temp = result.get(level);
    			//偶数行的从左到右，奇数行的从右到左
    			temp.add((level & 1) == 0 ? temp.size() : 0, node.val);
    		}
        	
        	zigzagLevelOrder(node.left, level + 1, result);
        	zigzagLevelOrder(node.right, level + 1, result);
        }
        
        //方法二：BFS
        public List<List<Integer>> zigzagLevelOrder2(TreeNode root) { 
        	List<List<Integer>> result = new ArrayList<>();
        	if(root == null) return result;
        	
        	LinkedList<TreeNode> queue = new LinkedList<>();
        	queue.offer(root);
        	int level = 0;
        	while(!queue.isEmpty()) { 
        		List<Integer> temp = new LinkedList<>();
        		for(int size = queue.size(); size > 0; size--) { 
        			TreeNode node = queue.pop();
        			//偶数行的从左到右，奇数行的从右到左
        			temp.add((level & 1) == 0 ? temp.size() : 0, node.val);
        			if(node.left != null)
        				queue.offer(node.left);
        			if(node.right != null)
        				queue.offer(node.right);    			
        		}
        		result.add(temp);
        		level++;
        	}
            return result;
        }
        
    }

## Test ##

import static org.junit.Assert.*;
    
    import java.util.Arrays;
    
    import org.hamcrest.collection.IsEmptyCollection;
    import org.hamcrest.collection.IsIterableContainingInOrder;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class BinaryTreeZigzagLevelOrderTraversalTest { 
    
    	@Test
    	@SuppressWarnings("unchecked")
    	public void test() { 
    		BinaryTreeZigzagLevelOrderTraversal obj = new BinaryTreeZigzagLevelOrderTraversal();
    
    		TreeNode root1 = BinaryTree.integers2BinaryTree(3,9,20,null,null,15,7);
    		assertThat(obj.zigzagLevelOrder(root1), // 
    				IsIterableContainingInOrder.contains(Arrays.asList(3), Arrays.asList(20, 9), Arrays.asList(15,7)));
    		
    		TreeNode root2 = BinaryTree.integers2BinaryTree(1);
    		assertThat(obj.zigzagLevelOrder(root2), // 
    				IsIterableContainingInOrder.contains(Arrays.asList(1)));
    		
    		assertThat(obj.zigzagLevelOrder(null), IsEmptyCollection.empty());
    	}
    	
    	@Test
    	@SuppressWarnings("unchecked")
    	public void test2() { 
    		BinaryTreeZigzagLevelOrderTraversal obj = new BinaryTreeZigzagLevelOrderTraversal();
    		
    		TreeNode root1 = BinaryTree.integers2BinaryTree(3,9,20,null,null,15,7);
    		assertThat(obj.zigzagLevelOrder2(root1), // 
    				IsIterableContainingInOrder.contains(Arrays.asList(3), Arrays.asList(20, 9), Arrays.asList(15,7)));
    		
    		TreeNode root2 = BinaryTree.integers2BinaryTree(1);
    		assertThat(obj.zigzagLevelOrder2(root2), // 
    				IsIterableContainingInOrder.contains(Arrays.asList(1)));
    		
    		assertThat(obj.zigzagLevelOrder2(null), IsEmptyCollection.empty());
    	}
    }

[https_leetcode.com_problems_binary-tree-zigzag-level-order-traversal]: https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
[788a88ab78ebe886286d553023e6c9c9.png]: /images/20221005/ac79a4020b9447748a3fac4c9c43c5d3.png