✅二叉树的层序遍历

接下来我们再来介绍二叉树的另一种遍历方式：层序遍历。
层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。
需要借用一个辅助队列来实现，
原因是：队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而这种层序遍历方式就是**图论中的广度优先遍历，**只不过我们应用在二叉树上。
使用队列实现二叉树广度优先遍历，动画如下：
102二叉树的层序遍历.gif

这样就实现了层序从左到右遍历二叉树。
本题可以作为二叉树层序遍历的模板，打十个就靠它了。

102.二叉树的层序遍历
107.二叉树的层次遍历II
199.二叉树的右视图
637.二叉树的层平均值
429.N叉树的层序遍历
515.在每个树行中找最大值
116.填充每个节点的下一个右侧节点指针
117.填充每个节点的下一个右侧节点指针II （待做）
104.二叉树的最大深度（待做）
111.二叉树的最小深度（待做）

层序遍历题目：（认真写完这十题，梦里全是层序遍历?）

102 二叉树的层序遍历

public List<List<Integer>> levelOrder(node root) {
    List<List<Integer>> list = new ArrayList<>();
    // 判空
    if (root == null) return list;


    // 使用队列，根据每一层节点数量弹出元素并将其左右孩子入队
    Queue<node> queue = new LinkedList<>();
    queue.add(root);



    while (!queue.isEmpty()){

        // 记录当前队列长度（该层有多少元素），决定弹出多少元素
        int size = queue.size();
        ArrayList<Integer> list2 = new ArrayList<>();
        while (size-- != 0){
            // 弹出元素添加到list并且将其左右孩子入队
            node node = queue.poll();
            list2.add(node.val);
            // 注意：这里需要判断该节点是否有子节点，有子节点才加入
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        list.add(list2);
    }



    return list;
}

107 二叉树的层序遍历Ⅱ

public List<List<Integer>> levelOrderBottom(TreeNode root) {
    // 在102 二叉树的层序遍历基础上,最后反转list
    List<List<Integer>> list = new ArrayList<>();

    if (root == null) return list;


    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);


    while (!queue.isEmpty()){
        int size = queue.size();
        ArrayList<Integer> list2 = new ArrayList<>();



        for (int i = 0; i < size; i++) {
            // 弹出上一层节点,添加其左右子节点(有的情况下)
            TreeNode node = queue.poll();

            list2.add(node.val);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }


        list.add(list2);
    }
    Collections.reverse(list);
    return list;


}

199 二叉树的右视图

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> list = new ArrayList<>();

    if (root == null) return list;



    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);



    while (!queue.isEmpty()){

        int size = queue.size();



        // 当循环到最后一个元素时将元素加入队列中
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();

            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
            if (i == size - 1) list.add(node.val);
        }


    }

    return list;


}

637 二叉树的层平均值

public List<Double> averageOfLevels(TreeNode root) {
    List<Double> list = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();




    queue.add(root);
    while (!queue.isEmpty()){
        int size = queue.size();
        double sum = 0;
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            // 算该层之和
            // 注意:如果写sum += node.val / size 会有误差
            sum += node.val;
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        // 将平均数添加到list
        list.add(sum / size);
    }


    return list;
}

429 N叉树的层序遍历

public List<List<Integer>> levelOrder(Node root) {
    // 变化是在第二层循环中,入队方式:用list的遍历方法入队(条件:!children.isEmpty)
    List<List<Integer>> list = new ArrayList<>();

    // 判空
    if (root == null) return list;
    // 使用队列，根据每一层节点数量弹出元素并将其左右孩子入队
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);


    while (!queue.isEmpty()){
        // 记录当前队列长度（该层有多少元素），决定弹出多少元素
        int size = queue.size();
        ArrayList<Integer> list2 = new ArrayList<>();
        for (int i = 0;i < size; i++){
            // 弹出元素添加到list并且将其左右孩子入队
            Node node = queue.poll();
            list2.add(node.val);
            // 注意：这里需要判断该节点是否有子节点，有子节点才加入
            if (!node.children.isEmpty()){
                queue.addAll(node.children);
            }
        }
        list.add(list2);
    }


    return list;
}

515 在每个树行中找最大值

public List<Integer> largestValues(TreeNode root) {
            // 两种方法，一种是在出队时用Math函数取Max
            // 一种可以根据之前逻辑,每次遍历一层后用工具类collections对list取最大值后放入res数组




            // 在102 二叉树的层序遍历基础上,最后反转list
            List<Integer> list = new ArrayList<>();
//            List<Integer> res = new ArrayList<>();
            if (root == null) return list;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                int size = queue.size();
                int max = Integer.MIN_VALUE;
                for (int i = 0; i < size; i++) {
                    // 弹出上一层节点,添加其左右子节点(有的情况下)
                    TreeNode node = queue.poll();
                    max = Math.max(node.val, max);



                    if (node.left != null) queue.add(node.left);
                    if (node.right != null) queue.add(node.right);
                }
//                Integer max = Collections.max(list);
//                res.add(max);
//                list.clear();


                list.add(max);
            }

            return list;
        }

116 填充每个节点的下一个右侧节点指针

public Node connect(Node root) {
    Queue<Node> queue = new LinkedList<>();
    if (root != null) queue.add(root);




    while (queue.size() != 0){
        int size = queue.size();


        // 先预留节点,指向接下来节点
        Node node = queue.poll();
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);

        // 循环 - 结束后指向该层最后一个节点
        for (int i = 1; i < size; i++) {
            Node next = queue.poll();
            if (next.left != null) queue.add(next.left);
            if (next.right != null) queue.add(next.right);



            node.next = next;
            node = next;
        }
    }

    return root;
}

✅226 翻转二叉树

如果要从整个树来看，翻转还真的挺复杂，整个树以中间分割线进行翻转，如图：

可以发现想要翻转它，其实就把每一个节点的左右孩子交换一下就可以了。
关键在于遍历顺序，前中后序应该选哪一种遍历顺序？（一些同学这道题都过了，但是不知道自己用的是什么顺序）
遍历的过程中去翻转每一个节点的左右孩子就可以达到整体翻转的效果。
注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果
**这道题目使用前序遍历和后序遍历都可以，唯独中序遍历不方便，**因为中序遍历会把某些节点的左右孩子翻转了两次！因此需要遍历两次left(具体可画图,更容易理解)
那么层序遍历可以不可以呢？依然可以的！只要把每一个节点的左右孩子翻转一下的遍历方式都是可以的！

递归法

对于二叉树的递归法的前中后序遍历，已经在二叉树的迭代遍历详细讲解了。
我们下文以前序遍历为例，通过动画来看一下翻转的过程:
图片[2]-羊羊刷题笔记Day14/60 | 第六章二叉树P2 | 二叉树的层序遍历、226. 翻转二叉树、101. 对称二叉树-五八三
我们来看一下递归三部曲：

确定递归函数的参数和返回值

参数就是要传入节点的指针，不需要其他参数了/
返回值的话题目中给出的要返回root节点的指针，所以函数的返回类型为TreeNode。

public TreeNode invertTree(TreeNode root) {}

确定终止条件

当前节点为空的时候，就返回

if (root == NULL) return root;

确定单层递归的逻辑

因为是先前序遍历，所以先进行交换左右孩子节点，然后反转左子树，反转右子树。

// swapChildren(root); // 前序:中左右
invertTree(root.left);
invertTree(root.right);
swapChildren(root); // 后序:左右中

基于这递归三步法，代码基本写完，代码如下：

public TreeNode invertTree(TreeNode root) {
            if (root == null) return null;
//            swapChildren(root); // 前序:中左右
            invertTree(root.left);
            invertTree(root.right);
            swapChildren(root); // 后序:左右中
            return root;
        }


        /**
         * 交换两个左右节点
         * @param root
         */
        private void swapChildren(TreeNode root) {
            TreeNode node = root.left;
            root.left = root.right;
            root.right = node;
        }

总结

针对二叉树的问题，解题之前一定要想清楚究竟是前中后序遍历，还是层序遍历。
二叉树解题的大忌就是自己稀里糊涂的过了（因为这道题相对简单），但是也不知道自己是怎么遍历的。
这也是造成了二叉树的题目“一看就会，一写就废”的原因。
**针对翻转二叉树，我给出了一种递归，三种迭代（两种模拟深度优先遍历，一种层序遍历）的写法，**都是之前我们讲过的写法，融汇贯通一下而已。详见226 翻转二叉树其他解法?
大家一定也有自己的解法，但一定要成方法论，这样才能通用，才能举一反三！

✅101 对称二叉树

首先想清楚，判断对称二叉树要比较的是哪两个节点，要比较的可不是左右节点！
对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。
那么如何比较呢？
比较的是两个子树的里侧和外侧的元素是否相等。如图所示：

那么遍历的顺序应该是什么样的呢？
本题遍历只能是“后序遍历”(左右中)，因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。
正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，另一个树的遍历顺序是右左中。
其实后序也可以理解为是一种回溯，当然这是题外话，讲回溯的时候会重点讲的。
那么我们先来看看递归法的代码应该怎么写。

递归法

递归三部曲

确定递归函数的参数和返回值

因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。
返回值自然是bool类型。
代码如下：

public boolean isSymmetric(TreeNode root) {}

确定终止条件

要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！否则后面比较数值的时候就会操作空指针了。
节点为空的情况有：（注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点）

左节点为空，右节点不为空，不对称，return false
左不为空，右为空，不对称 return false
左右都为空，对称，返回true

此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：

左右都不为空，比较节点数值，不相同就return false

此时左右节点不为空，且数值也不相同的情况我们也处理了。
代码如下：
(具体判断逻辑可以互换,不影响最后结果)

if (left == null && right == null) return true;
if (left != null && right == null) return false;
if (left == null && right != null) return false;
if (left.val != right.val) return false;

确定单层递归的逻辑

此时才进入单层递归的逻辑，单层递归的逻辑就是处理左右节点都不为空，且数值相同的情况。

比较外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
比较内侧是否对称，传入左节点的右孩子，右节点的左孩子。
如果左右都对称就返回true ，有一侧不对称就返回false 。(&&运算)

完整代码:

public boolean isSymmetric(TreeNode root) {
    return compare(root.left, root.right);
}




private boolean compare(TreeNode left, TreeNode right) {
    // 判断左右：（空 空 - true）（x 空）（空 x）（x1 x2） - false
    if (left == null && right == null) return true;
    if (left != null && right == null) return false;
    if (left == null && right != null) return false;
    if (left.val != right.val) return false;



    // 只有左右相等才符合要求
    // 对比左节点左孩子与右节点右孩子(外侧节点是否相等)
    boolean compareOutside = compare(left.left, right.right);
    // 对比左节点右孩子与右节点左孩子(内侧节点是否相等)
    boolean compareInside = compare(left.right, right.left);
    return (compareInside && compareOutside);



}

当然给出的代码并不简洁，但是把每一步判断的逻辑都清楚的描绘出来了。
如果上来就看网上各种简洁的代码，看起来真的很简单，但是只是链式编程把多条语句归为一条，很多逻辑都掩盖掉了，而题解可能也没有把掩盖掉的逻辑说清楚。
盲目的照着抄，结果就是：发现这是一道“简单题”，稀里糊涂的就过了，但是真正的每一步判断逻辑未必想到清楚。