103. Binary Tree Zigzag Level Order Traversal.md

103. Binary Tree Zigzag Level Order Traversal

Question:

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

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

Thinking:

• Method:
  • 通过BFS，可以将每一行都存入。
  • 通过栈存储子结点，同时需要两个栈，正序的存入一个栈，逆序的存入另一个栈。
  • 通过一个标志位确定正序或是逆序。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null) return result;
        boolean order = true;
        Stack<TreeNode> q = new Stack<>();
        Stack<TreeNode> qr = new Stack<>();
        q.push(root);
        int size = 0;
        while(!q.isEmpty() || !qr.isEmpty()){
            if(order)
                size = q.size();
            else size = qr.size();
            List<Integer> temp = new ArrayList<>();
            for(int i = 0; i < size; i++){
                TreeNode node = null;
                if(order)
                    node = q.pop();
                else
                    node = qr.pop();
                temp.add(node.val);
                if(order){
                    if(node.left != null) qr.push(node.left);
                    if(node.right != null ) qr.push(node.right);
                }else{
                    if(node.right != null ) q.push(node.right);
                    if(node.left != null) q.push(node.left);
                }
            }
            order = !order;
            result.add(temp);
        }
        return result;
    }
}

二刷

二刷的时候还是觉得比较轻松，用两个栈结构来存储数据。第一次测试的时候，我在添加数据的时候忘记反转左右加入的顺序了，稍微改了一下就好了。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new LinkedList<>();
        if(root == null) return result;
        Stack<TreeNode> st1 = new Stack<>();
        Stack<TreeNode> st2 = new Stack<>();
        st1.push(root);
        boolean flag = true;
        while(!st1.isEmpty() || !st2.isEmpty()){
            Stack<TreeNode> st = null;
            Stack<TreeNode> save = null;
            if(flag){
                st = st1;
                save = st2;
            }else{
                st = st2;
                save = st1;
            } 
            List<Integer> res = new LinkedList<>();
            TreeNode node = null;
            while(!st.isEmpty()){
                node = st.pop();
                res.add(node.val);
                if(flag){
                    if(node.left != null) save.push(node.left);
                    if(node.right != null) save.push(node.right);
                }else{
                    if(node.right != null) save.push(node.right);
                    if(node.left != null) save.push(node.left);
                }
            }
            flag = !flag;
            result.add(res);
        }
        return result;
    }
}

Amazon session

• Method 1: BFS
  1. Not really necessary to use stack or other data structure.
  2. Use normal bfs, just remember to add values to list using reverse flag.

   /**
    * Definition for a binary tree node.
    * public class TreeNode {
    *     int val;
    *     TreeNode left;
    *     TreeNode right;
    *     TreeNode(int x) { val = x; }
    * }
    */
   class Solution {
   	public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
   		List<List<Integer>> result = new ArrayList<>();
   		if(root == null) return result;
   		Queue<TreeNode> q = new LinkedList<>();
   		q.offer(root);
   		boolean reverse = false;
   		while(!q.isEmpty()){
   			LinkedList<Integer> cur = new LinkedList<>();
   			Queue<TreeNode> next = new LinkedList<>();
   			while(!q.isEmpty()){
   				TreeNode node = q.poll();
   				if(!reverse) cur.add(node.val);
   				else cur.addFirst(node.val);
   				if(node.left != null) next.offer(node.left);
   				if(node.right != null) next.offer(node.right);
   			}
   			result.add(cur);
   			q = next;
   			reverse = !reverse;
   		}
   		return result;
   	}
   }