binary_tree_zigzag_level_order_traversal.md

#Binary Tree Zigzag Level Order Traversal

原題網址

題意：

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).

解題思路：使用level order traversal，再加上queue與stack的幫助。

程式碼如下，但有錯誤，待發現bug再回頭修正

public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
    
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    if (root == null) {
        return null;
    }
    
    int level = 1;
    Stack<TreeNode> stack = new Stack<TreeNode>();
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    Queue<TreeNode> traverseQ = new LinkedList<TreeNode>();
    
    traverseQ.offer(root);
    while (!traverseQ.isEmpty()) {
        int size = traverseQ.size();
        
        for (int i = 0; i < size; i++) {
            TreeNode cur = traverseQ.poll();
            if (level % 2 == 1) {
                queue.offer(cur);
            } else {
                stack.push(cur);
            }
            
            if (cur.left != null) {
                traverseQ.offer(cur.left);
            }
            
            if (cur.right != null) {
                traverseQ.offer(cur.right);
            }
        }
        
        List<Integer> tempRes = new ArrayList<Integer>();
        if (level % 2 == 1) {
            for (int i = 0; i < queue.size(); i++) {
                tempRes.add(queue.poll().val);
            }
        } else {
            for (int i = 0; i < stack.size(); i++) {
                tempRes.add(stack.pop().val);
            }
        }
        
        res.add(new ArrayList<Integer>(tempRes));
        level++;
    }
    
    return res;
}

---

網友 喜刷刷 的解法

解題思路：利用兩個 Stack 不斷的交替使用，由於 Stack 是先進後出，籍由判斷 leftToRight 變數來決定存放的順序，接著再把兩個 stack 交換。

public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
    
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    
    if (root == null) {
        return res;
    }
    
    Stack<TreeNode> curLevel = new Stack<TreeNode>();
    Stack<TreeNode> nextLevel = new Stack<TreeNode>();
    curLevel.push(root);
    boolean leftToRight = true;
    
    while (!curLevel.isEmpty()) {
        ArrayList<Integer> tempRes = new ArrayList<Integer>();
        
        while (!curLevel.isEmpty()) {
            TreeNode cur = curLevel.pop();
            tempRes.add(cur.val);
            
            if (leftToRight) {
                if (cur.left != null) {
                    nextLevel.push(cur.left);
                }
                if (cur.right != null) {
                    nextLevel.push(cur.right);
                }
            } else {
                if (cur.right != null) {
                    nextLevel.push(cur.right);
                }
                if (cur.left != null) {
                    nextLevel.push(cur.left);
                }
            }
        }
        res.add(tempRes);
        Stack<TreeNode> temp = curLevel;
        curLevel = nextLevel;
        nextLevel = temp;
        leftToRight = !leftToRight;
        
    }
    
    return res;
}

---

另一解法：仍然按照level order traversal來遍歷整顆樹，接下來再把對應的列來作反轉的動作，時間複雜度較高。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        res = new ArrayList<List<Integer>>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<Integer>();
            for (int i = 0; i < size; i++) {
                TreeNode current = queue.poll();
                list.add(current.val);
                if (current.left != null) {
                    queue.offer(current.left);
                }
                if (current.right != null) {
                    queue.offer(current.right);
                }
            }
            res.add(new ArrayList<Integer>(list));
        }
        
        for (int i = 1; i < res.size(); i = i + 2) {
            List<Integer> list = reverse(res.get(i));
            res.set(i, list);
        }
        return res;
    }
    
    private List<Integer> reverse(List<Integer> list) {
        int start = 0;
        int end = list.size() - 1;
        while (start < end) {
            int temp = list.get(start);
            list.set(start, list.get(end));
            list.set(end, temp);
            start++;
            end--;
        }
        return list;
    }
}