【牛客 - 剑指offer】JZ77 按之字形顺序打印二叉树 Java实现

文章目录

剑指offer题解汇总 Java实现
本题链接
题目
方案一非递归层次遍历 LinkedList
方案二双栈法
- 我的代码
- 官方代码

剑指offer题解汇总 Java实现

https://blog.csdn.net/guliguliguliguli/article/details/126089434

本题链接

知识分类篇 - 树 - JZ77 按之字形顺序打印二叉树

题目

在这里插入图片描述
题目主要信息

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

方案一非递归层次遍历 LinkedList

队列相关知识点

队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。它满足先进先出的性质，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个元素作为新的队首。

我的思路

需要知道：根节点的深度为0

根据题意，深度为偶数的该层节点，是按照从左到右的顺序输出；深度为奇数的该层节点，是按照从右到左得到顺序输出

ArrayList的底层是通过一个动态的Object[]数组实现的，而LinkedList的底层是通过链表来实现的，因此它的随机访问速度是比较差的，但是它的删除，插入操作很快。

用变量depth来记录当前的深度

每到新的一层时，都会创建一个arrayList，记录当前这一层的遍历顺序，作为最终返回值的一部分

当depth为奇数时：不断取出LinkedList的最后一个元素，添加到arrayList中，然后按照右子节点，左子节点的顺序向LinkedList的头部添加新的元素

当depth为偶数时：不断取出LinkedList的第一个元素，添加到arrayList中，然后按照左子节点、右子节点的顺序向LinkedList的尾部添加新的元素

在这里插入图片描述

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 {

    private ArrayList<ArrayList<Integer>> lists = new ArrayList<>();

    private LinkedList<TreeNode> linkedList = new LinkedList<>();

    //根节点的深度是0
    int depth = 0;

    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {

        if (pRoot == null) {
            return lists;
        }

        linkedList.add(pRoot);

        TreeNode node;
        while (!linkedList.isEmpty()) {

            //当前linkedList的大小
            int n = linkedList.size();

            //存储这一层的节点
            ArrayList<Integer> list = new ArrayList<>();

            //深度为偶数，从左到右
            if ((depth & 1) == 0) {
                for (int i = 0; i < n; i++) {

                    node = linkedList.removeFirst();

                    list.add(node.val);

                    if (node.left != null) {
                        linkedList.addLast(node.left);
                    }
                    if (node.right != null) {
                        linkedList.addLast(node.right);
                    }
                }

            } else {
                //深度为奇数，从右到左
                for (int i = 0; i < n; i++) {

                    node = linkedList.removeLast();

                    list.add(node.val);

                    if (node.right != null) {
                        linkedList.addFirst(node.right);
                    }
                    if (node.left != null) {
                        linkedList.addFirst(node.left);
                    }
                }
            }
            depth++;
            lists.add(list);
        }
        return lists;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

牛客官方解答

按照层次遍历按层打印二叉树的方式，每层分开打印，然后对于每一层利用flag标记，第一层为false，之后每到一层取反一次，如果该层的flag为true，则记录的数组整个反转即可

还有，每层的节点数等于进入该层时队列的长度，因为刚进入该层时，这一层每个节点都已经push进队列，而上一层的节点都已经出去了

具体做法

首先判断二叉树是否为空，空树没有打印结果
建立辅助队列，根节点首先进入队列。不管层次怎么访问，根节点一定是第一个，那它肯定排在队伍的最前面，初始化flag变量
每次进入一层，统计队列中的元素个数，更改flag变量的值。因为每当访问完一层，下一层作为这一层的子节点，一定都加入队列，而再下一层还没有加入，因此此时队列中的元素个数就是这一层的元素个数
每次遍历这一层的节点数，将其依次从队列中弹出，然后加入这一行的一维数组中，如果它们有子节点，依次加入队列排队等待访问
访问完这一层元素后，根据flag变量，决定将这一个一维数组直接加入二维数组中还是反转后再加入，然后再访问下一层

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {

        ArrayList<ArrayList<Integer>> res = new ArrayList<>();

        if (pRoot == null) {
            //如果是空，则直接返回空list
            return res;
        }

        //队列存储，进行层次遍历
        Queue<TreeNode> temp = new LinkedList<>();

        temp.add(pRoot);

        TreeNode p;
        boolean flag = true;

        while (!temp.isEmpty()) {
            //记录二叉树的某一行
            ArrayList<Integer> row = new ArrayList<>();

            int n = temp.size();

            //奇数行反转，偶数行不反转
            flag = !flag;
            //因先进入的是根节点，故每层节点多少，队列大小就是多少
            for (int i = 0; i < n; i++) {

                //poll:删除并返回第一个元素
                p = temp.poll();

                row.add(p.val);

                //若是左右孩子存在，则存入左右孩子作为下一个层次
                if (p.left != null) {
                    temp.add(p.left);
                }

                if (p.right != null)
                    temp.add(p.right);
            }
            //奇数行反转，偶数行不反转
            if (flag) {
                Collections.reverse(row);
            }

            res.add(row);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

方案二双栈法

栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底

元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素
元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，是其相邻的元素成为新的栈顶元素

利用两个栈遍历这棵二叉树

第一个栈s1从根节点开始记录第一层，然后依次遍历两个栈，遍历第一个栈时，遇到的子节点依次加入第二个栈中
遍历第二个栈的时候，因为是先进后出，因此就是逆序的，再将第二个站的子节点依次加入第一个栈中

于是，原本的逆序在第一个栈中又变回了正序，如果反序交替直到两个栈都空为止