✅二叉树的层序遍历

接下来咱们再来介绍二叉树的另一种遍历办法：层序遍历。 层序遍历一个二叉树。便是从左到右一层一层的去遍历二叉树。这种遍历的办法和咱们之前讲过的都不太相同。 需求借用一个辅助行列来完成， 原因是：行列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模仿深度优先遍历也便是递归的逻辑。 而这种层序遍历办法便是**图论中的广度优先遍历，**只不过咱们应用在二叉树上。 运用行列完成二叉树广度优先遍历，动画如下：

这样就完成了层序从左到右遍历二叉树。 本题能够作为二叉树层序遍历的模板，打十个就靠它了。

• 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 翻转二叉树

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

递归法

关于二叉树的递归法的前中后序遍历，已经在二叉树的迭代遍历具体讲解了。 咱们下文以前序遍历为例，经过动画来看一下翻转的过程:

1. 确认递归函数的参数和回来值

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

public TreeNode invertTree(TreeNode root) {}

2. 确认停止条件

当时节点为空的时分，就回来

if (root == NULL) return root;

3. 确认单层递归的逻辑

由于是先前序遍历，所以先进行交流左右孩子节点，然后回转左子树，回转右子树。

// 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 对称二叉树

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

递归法

递归三部曲

1. 确认递归函数的参数和回来值

由于咱们要比较的是根节点的两个子树是否是彼此翻转的，进而判别这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。 回来值自然是bool类型。 代码如下：

public boolean isSymmetric(TreeNode root) {}

2. 确认停止条件

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

• 左节点为空，右节点不为空，不对称，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;

3. 确认单层递归的逻辑

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

• 比较外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
• 比较内侧是否对称，传入左节点的右孩子，右节点的左孩子。
• 假如左右都对称就回来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);
}

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

总结

这次咱们又深度剖析了一道二叉树的“简单题”，咱们会发现，真实的把标题搞清楚其实并不简单，leetcode上accept了和真实把握了仍是有距离的。 咱们介绍了递归法，递归仍然经过递归三部曲来处理了这道标题，假如只看精简的代码底子看不出来递归三部曲是如何解题的。(迭代法详看迭代法)

学习材料：

层序遍历

226 翻转二叉树

101 对称二叉树