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

川长思鸟来 2022-12-16 06:15 81阅读 0赞

# 题目 #

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

例如:  
给定二叉树: \[3,9,20,null,null,15,7\],  
![在这里插入图片描述][2020101909113791.png_pic_center]  
返回其层次遍历结果：  
![在这里插入图片描述][20201019091151652.png_pic_center]  
提示：  
节点总数 <= 1000

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof][https_leetcode-cn.com_problems_cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof]

# 解题思路 #

本质上还是二叉树的层序遍历+奇数层正序,偶数层倒序

二叉树的层序遍历?  
使用队列来解决

奇数层正序+偶数层倒序?  
使用双端队列来解决,即奇数层使用尾插法,偶数层使用头插法

如何判断当前层数是奇数层还是偶数层?  
结果集合的size%2,为0说明当前是奇数层,不为0说明当前为偶数层

# 代码 #

/** * 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>> list = new ArrayList<>();
            // 校验
            if (root == null) { 
                return list;
            }
    
            // 创建一个队列
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.add(root);
    
            while (!queue.isEmpty()) { 
                LinkedList<Integer> tempList = new LinkedList<>();
                // 用来标识当前是奇数层还是偶数层
                boolean flag = list.size() % 2 == 0;
                int size = queue.size();
                while (size > 0) { 
                    TreeNode node = queue.poll();
                    if (flag) { 
                        // 奇数层在尾部添加
                        tempList.addLast(node.val);
                    } else { 
                        // 偶数层在头部添加
                        tempList.addFirst(node.val);
                    }
    
                    if (node.left != null) { 
                        queue.add(node.left);
                    }
                    if (node.right != null) { 
                        queue.add(node.right);
                    }
                    size--;
                }
                list.add(tempList);
            }
    
            return list;
        }
    }

[2020101909113791.png_pic_center]: /images/20221123/a89fcbd824ad4af0aed8cdd61ef071f0.png
[20201019091151652.png_pic_center]: /images/20221123/75bffbf770fb46c78a4273aaade9a194.png
[https_leetcode-cn.com_problems_cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof]: https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof