代码随想录算法训练营day15||二叉树part02、102.二叉树的层序遍历、 226.翻转二叉树（优先掌握递归）、101. 对称二叉树（优先掌握递归）

102.二叉树的层序遍历

题目：给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。

接下来我们再来介绍二叉树的另一种遍历方式：层序遍历。

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

使用队列实现二叉树广度优先遍历，动画如下：

class Solution {
    //定义了一个名为resList 的成员变量，类型为List<List<Integer>>，用于存储层序遍历结果。
    //这个成员变量是一个二维列表，每个元素是一个!列表!，表示二叉树的一层节点值。
    public List<List<Integer>> resList = new ArrayList<List<Integer>>();

    //定义了一个名为levelOrder的公共方法，该方法接受一个TreeNode类型的参数root，表示二叉树的根节点。
    //该方法的返回类型是List<List<Integer>>，表示二叉树的层序遍历结果。
    public List<List<Integer>> levelOrder(TreeNode root) {
        checkFun02(root);//调用checkFun02 方法进行层序遍历。
        return resList;
    }

    //定义了一个名为checkFun02 的方法，用于实现二叉树的层序遍历。
    //首先检查当前节点node 是否为空，如果为空，则直接返回，表示无需进行层序遍历。
    public void checkFun02(TreeNode root){
        if(root == null) return;

        //创建一个名为que的队列，用于存储待访问的节点，并将根节点root入队列。
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.offer(root);//offer()：将元素添加到队尾，如果成功，则返回true。
        
        //使用循环来遍历队列中的节点，直到队列为空为止。
        while(!que.isEmpty()){
            //在内层循环中，首先创建一个名为itemList的列表，用于存储当前层的节点值，
            //并获取当前队列的大小，表示当前层的节点个数。
            List<Integer> itemList = new ArrayList<Integer>();
            int len = que.size();
            //这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            while(len > 0){
              //从队列中弹出一个节点tmpNode，并将其值添加到当前层的列表itemList中。
                TreeNode tmpNode = que.poll();//poll()：将队首的元素删除，并返回该元素。
                itemList.add(tmpNode.val); 
                if(tmpNode.left != null)  que.offer(tmpNode.left);
                if(tmpNode.right != null)  que.offer(tmpNode.right);
                len--;
            }
            //当前层的所有节点都处理完毕后，将当前层的列表itemList添加到结果列表resList中，并进入下一层的处理。
            resList.add(itemList);
        }
       
    }
    //至此，二叉树的层序遍历完成，结果存储在成员变量resList中，返回给调用者。
}

107.二叉树的层次遍历 II

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

思路：相对于102.二叉树的层序遍历，就是最后把result数组反转一下就可以了。

class Solution {
    public List<List<Integer>> resList = new ArrayList<List<Integer>>();

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        //checkFun01(root,0);
        checkFun02(root);

        //创建一个新的二维列表 result，用于存储按自底向上顺序排列的层序遍历结果。
        List<List<Integer>> result = new ArrayList<>();
        //使用循环遍历原始的层序遍历结果 resList，从最后一层开始，逐层向上遍历。
        //在遍历过程中，将每一层的节点列表添加到 result 中。
        for (int i = resList.size() - 1; i >= 0; i-- ) {
            result.add(resList.get(i));
        }
        return result;//返回按自底向上顺序排列的层序遍历结果列表 result。
    }
 public void checkFun02(TreeNode node) {
        if (node == null) return;
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.offer(node);

        while (!que.isEmpty()) {
            List<Integer> itemList = new ArrayList<Integer>();
            int len = que.size();

            while (len > 0) {
                TreeNode tmpNode = que.poll();
                itemList.add(tmpNode.val);

                if (tmpNode.left != null) que.offer(tmpNode.left);
                if (tmpNode.right != null) que.offer(tmpNode.right);
                len--;
            }

            resList.add(itemList);
        }

    }
}

在102基础上稍作改动：

//创建一个新的二维列表 result，用于存储按自底向上顺序排列的层序遍历结果。

List<List<Integer>> result = new ArrayList<>();

//使用循环遍历原始的层序遍历结果 resList，从最后一层开始，逐层向上遍历。

//在遍历过程中，将每一层的节点列表添加到 result 中。

for (int i = resList.size() - 1; i >= 0; i-- ) {

result.add(resList.get(i));

}

return result; //返回按自底向上顺序排列的层序遍历结果列表 result。

199.二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

思路：层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。

class Solution {
    /**
     * 解法：队列，迭代。
     * 每次返回每层的最后一个字段即可。
     * 小优化：每层右孩子先入队。代码略。
     */
     public List<Integer> rightSideView(TreeNode root) {
//定义了一个名为rightSideView的公共方法，该方法接受一个TreeNode类型的参数root，表示二叉树的根节点。
//该方法的返回类型是List<Integer>，表示二叉树每层最右侧节点的值。

        //创建一个名为 resList 的列表，用于存储每层最右侧节点的值。
        List<Integer> resList = new ArrayList<>();
        //创建一个名为 que 的双端队列，用于进行层序遍历。
        //这里选择双端队列的原因是为了让每层的右孩子先入队，以便后续直接取出最后一个节点。
        Deque<TreeNode> que = new LinkedList<>();
    
        //如果根节点为空，则直接返回空列表。
        if (root == null) {
            return resList;
        }
        //将根节点入队。
        que.offerLast(root);
        //使用循环遍历队列中的节点，直到队列为空为止。
         while (!que.isEmpty()) {
            //获取当前层的节点数levelSize，并使用内层循环遍历当前层的所有节点。
            int levelSize = que.size();
            //从队列中弹出一个节点tmpNode，并将其左右孩子节点依次入队。
            for (int i = 0; i < levelSize; i++) {
                TreeNode tmpNode = que.pollFirst();

                if (tmpNode.left != null) {
                    que.addLast(tmpNode.left);
                }
                if (tmpNode.right != null) {
                    que.addLast(tmpNode.right);
                }
                //如果当前节点是当前层的最后一个节点，则将其值添加到结果列表resList中。
                if (i == levelSize - 1) {
                    resList.add(tmpNode.val);
                } 
                //继续处理下一层的节点。
            }
        }
        return resList;//返回存储了每层最右侧节点值的列表resList。
    }
}

637.二叉树的层平均值

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

思路：本题就是层序遍历的时候把一层求个总和在取一个均值。

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        //定义了一个名为averageOfLevels 的公共方法，该方法接受一个TreeNode类型的参数root，表示二叉树的根节点。
        //该方法的返回类型是List<Double>，表示二叉树每层节点值的平均值。

        //创建一个名为resList的列表，用于存储每层节点值的平均值。
        List<Double> resList = new ArrayList<>();
        //创建一个名为 que 的双端队列，用于进行层序遍历。
        Deque<TreeNode> que = new LinkedList<>();

        if(root == null){
            return resList;
        }
        //将根节点入队。
        que.offerLast(root);
        //使用循环遍历队列中的节点，直到队列为空为止。
        while(!que.isEmpty()){
            //获取当前层的节点数levelSize，并使用内层循环遍历当前层的所有节点。
            int levelSize = que.size();
            double levelSum = 0.0;
            for(int i = 0; i < levelSize; i++){
                //从队列中弹出一个节点poll，并将其值加到当前层的和levelSum 中。
                TreeNode tmpNode = que.pollFirst();
                levelSum += tmpNode.val;
                //然后将其左右孩子节点依次入队。
                if(tmpNode.left != null) que.addLast(tmpNode.left);
                if(tmpNode.right != null) que.addLast(tmpNode.right);
        }
        resList.add(levelSum / levelSize);//计算当前层节点值的平均值，并将其添加到结果列表resList中。
    }
    return resList;//返回存储了每层节点值平均值的列表list。
    }
}

429.N叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。

思路：这道题依旧是模板题，只不过一个节点有多个孩子了

515.在每个树行中找最大值

您需要在二叉树的每一行中找到最大的值。

思路：层序遍历，取每一层的最大值

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

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

思路：本题依然是层序遍历，只不过在单层遍历的时候记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点就可以了

117.填充每个节点的下一个右侧节点指针II

思路：这道题目说是二叉树，但116题目说是完整二叉树，其实没有任何差别，一样的代码一样的逻辑一样的味道

104.二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：给定二叉树 [3,9,20,null,null,15,7]，

111.二叉树的最小深度

思路：相对于 104.二叉树的最大深度，本题还也可以使用层序遍历的方式来解决，思路是一样的。需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

总结：

二叉树的层序遍历，就是图论中的广度优先搜索在二叉树中的应用，需要借助队列来实现（此时又发现队列的一个应用了）。

来吧，一口气打十个：

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

226.翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

题外话：这道题目是非常经典的题目，也是比较简单的题目（至少一看就会）。

但正是因为这道题太简单，一看就会，一些同学都没有抓住起本质，稀里糊涂的就把这道题目过了。如果做过这道题的同学也建议认真看完，相信一定有所收获！

注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果

这道题目使用前序遍历和后序遍历都可以，唯独中序遍历不方便，因为中序遍历会把某些节点的左右孩子翻转了两次！建议拿纸画一画，就理解了

那么层序遍历可以不可以呢？依然可以的！只要把每一个节点的左右孩子翻转一下的遍历方式都是可以的！

递归法：

class Solution {
    //递归法
/** 前后序遍历都可以
    （这里代码给出的后序遍历，先递归处理左子树，然后递归处理右子树，最后再处理根节点。）
  * 中序不行，因为先左孩子交换孩子，再根交换孩子（做完后，右孩子已经变成了原来的左孩子），
    再右孩子交换孩子（此时其实是对原来的左孩子做交换）
*/
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {//递归终止条件
            return root;
        }
        //递归地对当前节点的左右子树进行反转，即先对左子树进行反转，再对右子树进行反转。
        invertTree(root.left);
        invertTree(root.right);
        swapChildren(root); //调用swapChildren 方法交换当前节点的左右子节点。

        return root;//返回反转后的二叉树的根节点。
    } 
    //定义了一个私有方法swapChildren，用于交换节点的左右子节点。
    //这个方法接受一个节点root，将其左右子节点进行交换
    private void swapChildren(TreeNode root){
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }
}