題⽬描述

請實現⼀個函數按照之字形打印⼆叉樹，即第⼀⾏按照從左到右的順序打印，第⼆層按照從右⾄左的順序打印，第三⾏按照從左到右的順序打印，其他⾏以此類推。

示例1
輸⼊：{8,6,10,5,7,9,11}
返回值：[[8],[10,6],[5,7,9,11]]

思路及解答

雙向鏈表（推薦）

1. 藉助雙向鏈表，初始化⼀個添加⽅向 boolean 值，先將根節點添加進去：
2. 獲取 list ⾥⾯剩下的元素的個數，挨個取出就是⼀層，取出的時候，如果 reverse 為 true ，則往鏈表的第 0 個索引位置添加，否則直接在後⾯添加，然後判斷每⼀個取出來的節點的左右節點是不是為空，不為空則加⼊鏈表。
3. 每⼀層處理完之後，將 list 加⼊結果集中，然後翻轉 reverse 的值，繼續判斷 list 是不是為空，執⾏第⼆步循環。

public class Solution {
    public ArrayList < ArrayList < Integer >> Print(TreeNode pRoot) {
        LinkedList < TreeNode > nodes = new LinkedList < > ();
        ArrayList < ArrayList < Integer >> results = new ArrayList();
        boolean reverse = true;
        if (pRoot != null) {
            nodes.add(pRoot);
            while (!nodes.isEmpty()) {
                ArrayList < Integer > integers = new ArrayList();
                int size = nodes.size();
                for (int i = 0; i < size; i++) {
                    TreeNode node = nodes.poll();
                    if (reverse) {
                        integers.add(node.val);
                    } else {
                        integers.add(0, node.val);
                    }
                    if (node.left != null) {
                        nodes.offer(node.left);
                    }
                    if (node.right != null) {
                        nodes.offer(node.right);
                    }
                }
                if (integers.size() != 0) {
                    results.add(integers);
                }
                reverse = !reverse;
            }
        }
        return results;
    }
}

• 空間複雜度由於藉助了額外的 list ，為 O(n)
• 時間複雜度，由於每個節點進⼊隊列⼜出來，為 O(2n) ，也是 O(n) 。

隊列 + 方向反轉

這是最直接的方法。我們進行標準的層序遍歷，但用一個標誌位記錄當前層是奇數層還是偶數層。對於偶數層，我們在將該層的節點值列表加入最終結果前，先進行反轉

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (pRoot == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);
        boolean leftToRight = true; // 方向標誌，true表示從左到右

        while (!queue.isEmpty()) {
            int levelSize = queue.size(); // 當前層的節點數
            ArrayList<Integer> levelList = new ArrayList<>();

            // 遍歷當前層的所有節點
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                levelList.add(node.val); // 將節點值加入當前層列表

                // 將下一層的節點按標準順序（先左後右）加入隊列
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }

            // 如果是偶數層（從第0層開始算則為奇數索引），反轉當前層列表
            if (!leftToRight) {
                Collections.reverse(levelList);
            }
            result.add(levelList);
            leftToRight = !leftToRight; // 切換方向
        }
        return result;
    }
}

• 時間複雜度：O(n)。每個節點被訪問一次，對於偶數層，Collections.reverse的時間複雜度為 O(當前層節點數)，所有層的節點數相加為 n，因此總時間複雜度為 O(n)。
• 空間複雜度：O(n)。隊列和結果列表所需空間與節點數 n 成線性關係。

雙棧交替

利用棧後進先出（LIFO）的特性來自然地實現順序的反轉。我們使用兩個棧，一個用於處理當前層，另一個用於存儲下一層的節點

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (pRoot == null) return result;

        Stack<TreeNode> stack1 = new Stack<>(); // 處理奇數層（從左到右）
        Stack<TreeNode> stack2 = new Stack<>(); // 處理偶數層（從右到左）
        stack1.push(pRoot);

        // 當兩個棧都為空時，遍歷結束
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            ArrayList<Integer> levelList = new ArrayList<>();

            if (!stack1.isEmpty()) {
                // 處理stack1（奇數層），其子節點將以“從右到左”的順序壓入stack2
                while (!stack1.isEmpty()) {
                    TreeNode node = stack1.pop();
                    levelList.add(node.val);
                    // 關鍵：先左子節點後右子節點入棧，出棧順序則為先右後左
                    if (node.left != null) stack2.push(node.left);
                    if (node.right != null) stack2.push(node.right);
                }
            } else {
                // 處理stack2（偶數層），其子節點將以“從左到右”的順序壓入stack1
                while (!stack2.isEmpty()) {
                    TreeNode node = stack2.pop();
                    levelList.add(node.val);
                    // 關鍵：先右子節點後左子節點入棧，出棧順序則為先左後右
                    if (node.right != null) stack1.push(node.right);
                    if (node.left != null) stack1.push(node.left);
                }
            }
            result.add(levelList);
        }
        return result;
    }
}

• 時間複雜度：O(n)。每個節點被壓入棧和彈出棧各一次。
• 空間複雜度：O(n)。兩個棧在最壞情況下共同存儲 n 個節點。