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

太过爱你忘了你带给我的痛 2022-09-10 03:14 101阅读 0赞

> 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
> 
> 例如:  
> 给定二叉树: \[3,9,20,null,null,15,7\],
> 
> 3  
> / \\  
> 9 20  
> / \\  
> 15 7  
> 返回其层次遍历结果：
> 
> \[  
> \[3\],  
> \[20,9\],  
> \[15,7\]  
> \]  
> 
> 
> 提示：
> 
> 节点总数 <= 1000
> 
> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
          Queue<TreeNode> queue = new LinkedList<>();
            List<List<Integer>> res = new ArrayList<>();
            Boolean flag = true;
            if(root != null) queue.add(root);
            while(!queue.isEmpty()) {
                LinkedList<Integer> tmp = new LinkedList<>();
                for(int i = queue.size(); i > 0; i--) {
                    TreeNode node = queue.poll();
                    if(flag == true) {
                        tmp.addLast(node.val);
                    } 
                    else tmp.addFirst(node.val); 
                    if(node.left != null) queue.add(node.left);
                    if(node.right != null) queue.add(node.right);
                }
                res.add(tmp);
                flag = !flag;
            }
            return res;
        }
    }

[https://blog.csdn.net/qq\_35354855/article/details/119981794][https_blog.csdn.net_qq_35354855_article_details_119981794]

与上面这道题目不同的是，需要从上至下“之”字形打印每层的节点，那么就相当于每一层打印顺序不一样，每一层的打印顺序相反。

这样就好理解了，第一层正序打印，第二层倒序打印，修改一下文章中代码即可。

[https_blog.csdn.net_qq_35354855_article_details_119981794]: https://blog.csdn.net/qq_35354855/article/details/119981794?spm=1001.2014.3001.5501