#yyds干货盘点# 面试必刷TOP101：按之字形顺序打印二叉树

网络安全华佗 lv.1

发布时间：2022-10-16 04:10:21 356

相关标签：

1.简述：

描述

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

数据范围：,树上每个节点的val满足要求：空间复杂度：，时间复杂度：

例如：

给定的二叉树是{1,2,3,#,#,4,5}

#yyds干货盘点# 面试必刷TOP101：按之字形顺序打印二叉树_层序遍历_05

该二叉树之字形层序遍历的结果是

[

[1],

[3,2],

[4,5]

]

示例1

输入：

{1,2,3,#,#,4,5}

返回值：

[[1],[3,2],[4,5]]

说明：

如题面解释，第一层是根节点，从左到右打印结果，第二层从右到左，第三层从左到右。

示例2

输入：

{8,6,10,5,7,9,11}

返回值：

[[8],[10,6],[5,7,9,11]]

示例3

输入：

{1,2,3,4,5}

返回值：

[[1],[3,2],[4,5]]

2.代码实现：

public class Solution {
    public ArrayList Print(TreeNode pRoot) {
        Deque deque = new LinkedList<>();
        ArrayList res = new ArrayList<>();
        if(pRoot != null) deque.add(pRoot);
        while(!deque.isEmpty()) {
            // 打印奇数层
            ArrayListtmp = new ArrayList<>();
            for(int i = deque.size(); i > 0; i--) {
                // 从左向右打印
                TreeNode node = deque.removeFirst();
                tmp.add(node.val);
                // 先左后右加入下层节点
                if(node.left != null) deque.addLast(node.left);
                if(node.right != null) deque.addLast(node.right);
            }
            res.add(tmp);
            if(deque.isEmpty()) break; // 若为空则提前跳出
            // 打印偶数层
            tmp = new ArrayList<>();
            for(int i = deque.size(); i > 0; i--) {
                // 从右向左打印
                TreeNode node = deque.removeLast();
                tmp.add(node.val);
                // 先右后左加入下层节点
                if(node.right != null) deque.addFirst(node.right);
                if(node.left != null) deque.addFirst(node.left);
            }
            res.add(tmp);
        }
        return res;
    }

}

文章来源： https://blog.51cto.com/u_15488507/5604430

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。