剑指offer-- 32 - III. 从上到下打印二叉树 III

喜欢ヅ旅行 2023-02-23 12:28 10阅读 0赞

## 题目描述 ##

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

**例如:**  
给定二叉树: \[3,9,20,null,null,15,7\],

/  
9 20  
/  
15 7  
**返回其层次遍历结果：**

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

**提示：**

节点总数 <= 1000

## 思路：在II的基础上改进，将list的尾部添加->头部添加 ##

可以使用`addFirst()、addLast()` 是`LinkedList`数据结构特有的方法。

## 解决方法 ##

/**
     * 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>> levelOrder(TreeNode root) {
        
            List<List<Integer>> res = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
    
            if(root == null) return res;
            queue.offer(root);
            boolean flag = true;  //通过flag来标记每一行，是否需要头部添加
    
            while(queue.size() != 0){
        
                LinkedList<Integer> temp = new LinkedList<>();  //用于临时存储当前层打印结果；
                int size = queue.size();  //记录每一层的节点个数，queue的大小是动态变化的
    
                for(int i=0; i<size; i++){
        
                    TreeNode node = queue.poll();
                    if(flag == true){
        
                        temp.addLast(node.val);
                    }else{
        
                        temp.addFirst(node.val); //addFirst()属于LinkedList特有的方法，实现在头部添加
                    }
    
                    if(node.left != null)
                        queue.offer(node.left);
                    if(node.right != null)
                        queue.offer(node.right);
                }
                flag = !flag;  //每保存完一层,flag值取反
                res.add(temp);
            }
            return res;
        }
    }