NC14 按之字形顺序打印二叉树

题目链接：https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0

题目描述

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

数据范围：0 ≤ n ≤1500,树上每个节点的val满足 |val| <= 1500
要求：空间复杂度：O(n)，时间复杂度：O(n)

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

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

[

[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]]

解题代码

import java.util.*;
import java.util.ArrayList;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        TreeNode head = pRoot;
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (head == null)
            //如果是空，则直接返回空list
            return res;
        //队列存储，进行层次遍历
        Queue<TreeNode> temp = new LinkedList<TreeNode>();
        temp.offer(head);
        TreeNode p;
        boolean flag = true;
        while (!temp.isEmpty()) {
            //记录二叉树的某一行
            ArrayList<Integer> row = new ArrayList<Integer>();
            int n = temp.size();
            //奇数行反转，偶数行不反转
            flag = !flag;
            //因先进入的是根节点，故每层节点多少，队列大小就是多少
            for (int i = 0; i < n; i++) {
                p = temp.poll();
                row.add(p.val);
                //若是左右孩子存在，则存入左右孩子作为下一个层次
                if (p.left != null)
                    temp.offer(p.left);
                if (p.right != null)
                    temp.offer(p.right);
            }
            //奇数行反转，偶数行不反转
            if (flag)
                Collections.reverse(row);
            res.add(row);
        }
        return res;
    }
}

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名，转载请...
最后编辑时间为: 2022/08/11 11:12:14