📃 题目描述

题目链接：

• 剑指 Offer 32 - III. 从上到下打印二叉树 III (opens new window)
• 103. 二叉树的锯齿形层序遍历 (opens new window)

🔔 解题思路

方法一：队列 + reverse

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();

        if (root == null) {
            return res;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        // 记录行号
        int row = 1;
        while (!queue.isEmpty()) {
            int sz = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < sz; i ++) {
                TreeNode cur = queue.poll();
                list.add(cur.val);

                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }

            // 偶数行逆序
            if (row % 2 == 0) {
                Collections.reverse(list);
            }

            res.add(list);

            // 行号 ++
            row ++;
        }

        return res;
    }
}

方法二：双栈

• 维护两个栈，一个存放奇数层的节点，一个存放偶数层的节点
• 分奇数层和偶数层处理
  • 偶数层按顺序，每次奇数层的栈处理下一层偶数层的孩子节点，先存左结点，这样等下次 pop 时就是右节点先打印
  • 奇数层反序，每次偶数层的栈处理下一层奇数层节点，先存右结点，这样等下次 pop 时就是左节点先打印

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        
        if (root == null) {
            return res;
        }
        
        // 存储奇数层节点
        Stack<TreeNode> stack1 = new Stack<>();
        stack1.push(root);
        // 存储偶数层节点
        Stack<TreeNode> stack2 = new Stack<>();
        
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            if (!stack1.isEmpty()) {
                int size = stack1.size();
                for (int i = 0; i < size; i ++) {
                    TreeNode cur = stack1.pop();
                    list.add(cur.val);
                    
                    if (cur.left != null) {
                        stack2.push(cur.left);
                    }
                    if (cur.right != null) {
                        stack2.push(cur.right);
                    }
                }
            }
            else if (!stack2.isEmpty()) {
                int size = stack2.size();
                for (int i = 0; i < size; i ++) {
                    TreeNode cur = stack2.pop();
                    list.add(cur.val);
                    // 注意这里是先 push cur.right
                    if (cur.right != null) {
                        stack1.push(cur.right);
                    }
                    if (cur.left != null) {
                        stack1.push(cur.left);
                    }
                    
                }
            }
            
            res.add(list);
        }
        
        return res;
    }

}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：