代码随想录算法训练营第十五天| 二叉树的层序遍历、226.翻转二叉树、101.对称二叉树

系列文章目录

系列文章目录
二叉树层序遍历（10题）
- 102. 二叉树的层序遍历
- - ①DFS--递归方式
  - ②BFS--迭代方式--借助队列
- 107.二叉树的层次遍历 II
- 199.二叉树的右视图
- 637.二叉树的层平均值
- 429.N叉树的层序遍历
- - 遍历每个节点的子节点
- 515.在每个树行中找最大值
- 116.填充每个节点的下一个右侧节点指针
- 117.填充每个节点的下一个右侧节点指针II
- 104.二叉树的最大深度
- 111.二叉树的最小深度
226.翻转二叉树
- ①BFS层序遍历（广度优先遍历）
- ②中序统一迭代遍历（模拟深度优先遍历，前中后都可）
- ③DFS递归遍历（深度优先遍历，前序后序都可）
- - 中序不行原因
  - 前序（中节点需要交换左右子节点顺序，左右代表遍历方向）
  - 后序
101. 对称二叉树

二叉树层序遍历（10题）

102. 二叉树的层序遍历

①DFS–递归方式

递归遍历：一直访问到最深的节点，然后回溯到它的父节点，遍历另一条路径，直到遍历完所有节点，对应DFS（深度优先搜索），利用递归/栈实现。
DFS（Depth-First Search，深度优先搜索）：
①在 DFS 中，我们从起始节点开始，沿着一条路径一直往下搜索，直到无法继续为止。然后回溯到上一个节点，尝试探索其他路径。
②这意味着在遍历过程中，我们会尽可能地深入到图的一个分支中，直到到达末端节点，然后再返回并尝试其他分支。
③通常使用递归或栈来实现 DFS。

import java.util.LinkedList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    //类的属性可以被该类所有方法调用
    List<List<Integer>> resList = new LinkedList<>();//返回遍历结果
    public List<List<Integer>> levelOrder(TreeNode root) {
        checkFun01(root,0);
        return resList;
    }
    //DFS--递归方式
    public void checkFun01(TreeNode node,int deep){//确定递归函数的参数和返回值
        //确定终止条件
        if(node==null){
            return;
        }
        deep++;

        //确定单层递归的逻辑
            //当层级增加时，list的Item也增加，利用list的索引值进行层级界定
        if(resList.size()<deep){
            List<Integer> itemList = new LinkedList<>();//存放每一层的元素
            resList.add(itemList);
        }
        resList.get(deep-1).add(node.val);
        checkFun01(node.left,deep);
        checkFun01(node.right,deep);
    }
}

②BFS–迭代方式–借助队列

层序遍历：从上到下，从左到右，访问所有节点，对应BFS（广度优先搜索），利用队列实现。
BFS（Breadth-First Search，广度优先搜索）：
①在 BFS 中，我们从起始节点开始，首先访问起始节点，然后逐层地访问与起始节点相邻的节点。
②换句话说，BFS 会先遍历图的第一层节点，然后是第二层节点，以此类推，直到遍历完整个图。
③通常使用队列来实现 BFS。

①最后返回的链表resList 需作为类的属性，因其需被该类的所有访问。
②借助队列que实现遍历元素，当队列不为空（!que.isEmpty()）时说明节点还没有遍历完；
③在每一层遍历的时候，一定要使用固定大小的len，不要使用que.size()，因为que.size是不断变化的。（除了要将自己的值弹出来加入链表itemList 中，还要将自己的左右孩子放进队列que中，作为下一层遍历。）
③将每一层的元素放在一个链表itemList 里面，最后将每一层的itemList 加入到最终要返回的链表resList里面。

import java.util.LinkedList;
import java.util.List;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    //类的属性可以被该类所有方法调用
    List<List<Integer>> resList = new LinkedList<>();//返回遍历结果
    public List<List<Integer>> levelOrder(TreeNode root) {
        checkFun02(root);
        return resList;
    }

    //BFS--迭代方式--借助队列
    public void checkFun02(TreeNode root) {
        Queue<TreeNode> que = new LinkedList<>();

        //剪枝
        if (root == null) {
            return;
        }
        que.offer(root);
        while(!que.isEmpty()){//队列不为空说明还没遍历完
            List<Integer> itemList = new LinkedList<>();//存放每一层的元素
            int len = que.size();
            //将每一层的元素存入该层的链表
            while(len-->0){// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
                TreeNode node = que.poll();
                itemList.add(node.val);
                if(node.left!=null){
                    que.offer(node.left);
                } if(node.right!=null){
                    que.offer(node.right);
                }
            }
            resList.add(itemList);//将该层列表元素加入最终要返回的链表
        }
    }
}

107.二叉树的层次遍历 II

相对于 102.二叉树的层序遍历，就是最后把resList链表反转一下就可以了。
①使用Collections类的reverse方法直接反转。
②/利用链表LinkedList可以通过addFirst方法进行 O(1) 头部插入, 这样最后答案不需要再反转。因该方法是继承的接口Deque<>，故在定义要返回的链表resList 时不能再用 List<List<Integer>>，而应该用LinkedList<List<Integer>>，最后在将每一层元素加入链表resList 是要用addFirst即可。

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    //①
    List<List<Integer>> resList = new LinkedList<>();
    //②
    //LinkedList<List<Integer>> resList = new LinkedList<>();

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        bfsMethod(root);
        //①
        Collections.reverse(resList);
        return resList;
    }

    //BFS 借助队列迭代法
    public void bfsMethod(TreeNode node) {
        Deque<TreeNode> que = new ArrayDeque<>();
        //剪枝
        if (node == null) {
            return;
        }
        que.offer(node);
        while (!que.isEmpty()) {
            List<Integer> itemList = new LinkedList<>();
            int len = que.size();
            while (len-- > 0) {
                TreeNode tempNode = que.poll();
                itemList.add(tempNode.val);
                if (tempNode.left != null) {
                    que.offer(tempNode.left);
                }
                if (tempNode.right != null) {
                    que.offer(tempNode.right);
                }
            }
            //①
            resList.add(itemList);
            //②
            //resList.addFirst(itemList);
        }
    }
}

199.二叉树的右视图

注：当左子树比右子树长时，最右边的节点是左子树的右节点，故层序遍历也要加入左子树，不能只加入右子树，每次返回每层的最后一个字段即可。

import java.util.LinkedList;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> resList = new LinkedList<>();
        //BFS 使用队列迭代
        Queue<TreeNode> que = new LinkedList<>();
        if (root == null) {
            return resList;
        }
        que.offer(root);
        while (!que.isEmpty()) {
            int len = que.size();
            while (len-- > 0) {//先比较再自减
                TreeNode node = que.poll();
                if (node.left != null) {
                    que.offer(node.left);//必须也加入左节点，因也可能看见左节点的右子节点
                }
                if (node.right != null) {
                    que.offer(node.right);
                }
                //当遍历到最右边的元素时，len已经自减为0
                if (len == 0) {
                    resList.add(node.val);//只添加最右边的节点
                }
            }

            //for循环
/*            for (int i = 0; i < len; i++) {
                TreeNode node = que.poll();
                if (node.left != null) {
                    que.offer(node.left);
                }
                if (node.right != null) {
                    que.offer(node.right);
                }
                if (i == len - 1) {//加入最右边的节点
                    resList.add(node.val);
                }
            }*/
        }

        return resList;
    }
}

637.二叉树的层平均值

思路：将每一层的值加起来，最后除以每一层的元素个数，将这个值加入到返回链表resList 即可。

import java.util.LinkedList;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    List<Double> resList = new LinkedList<>();

    public List<Double> averageOfLevels(TreeNode root) {
        bfsMethod(root);
        return resList;
    }

    public void bfsMethod(TreeNode node) {
        Queue<TreeNode> que = new LinkedList<>();
        if (node == null) {
            return;
        }
        que.offer(node);
        while (!que.isEmpty()) {
            Double sum = 0.0;
            int len = que.size();
            for (int i = 0; i < len; i++) {
                TreeNode tempNode = que.poll();
                sum += tempNode.val;
                if (tempNode.left != null) que.offer(tempNode.left);
                if (tempNode.right != null) que.offer(tempNode.right);
            }
            resList.add(sum / len);
        }
    }
}

429.N叉树的层序遍历

import java.util.LinkedList;

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

    public List<List<Integer>> levelOrder(Node root) {
        bfsMethod(root);
        return resList;
    }

    public void bfsMethod(Node node) {
        Queue<Node> que = new LinkedList<>();
        if (node == null) {
            return;
        }
        que.offer(node);
        while (!que.isEmpty()) {
            List<Integer> itemList = new LinkedList<>();
            int len = que.size();
            for (int i = 0; i < len; i++) {
                Node tempNode = que.poll();
                itemList.add(tempNode.val);
                List<Node> children = tempNode.children;
/*                while (!children.isEmpty()) {
                    que.offer(children.remove(0));
                }*/
                //增强for循环，代码健壮性及剪枝处理
                if(children==null||children.size()==0){
                    continue;
                }
                for(Node child:children){
                    que.offer(child);
                }
                //普通for循环(先判断children不为空才能调用方法，否则会空指针异常)
/*                for (int j = 0; children != null && j < children.size(); j++) {
                    que.offer(children.get(j));
                }*/
            }
            resList.add(itemList);
        }
    }
}

遍历每个节点的子节点

通过while 判断每个节点的子节点链表children是否为空，不为空时，将子节点链表children第一个元素移除并将其加入队列que中。

                List<Node> children = tempNode.children;
                while (!children.isEmpty()) {
                    que.offer(children.remove(0));
                }

通过增强for循环来遍历子节点链表children的每个节点，并将其加入队列que中。

                List<Node> children = tempNode.children;
                //代码健壮性及剪枝处理
                if(children==null||children.size()==0){
                    continue;
                }
                for(Node child:children){
                    que.offer(child);
                }

3.普通for循环(先判断children不为null才能调用方法，否则会报空指针异常）

	            List<Node> children = tempNode.children;
                for (int j = 0; children != null && j < children.size(); j++) {
                    que.offer(children.get(j));
                }

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

注：找最大值时，可使用：
①三元运算符：maxNum = maxNum < tempNode.val ? tempNode.val : maxNum;
②Math类的max方法：maxNum=Math.max(maxNum,tempNode.val);

import java.util.LinkedList;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    List<Integer> resList = new LinkedList<>();

    public List<Integer> largestValues(TreeNode root) {
        dfsMethod(root);
        return resList;
    }

    public void dfsMethod(TreeNode node) {
        Queue<TreeNode> que = new LinkedList<>();
        if (node == null) {
            return;
        }
        que.offer(node);
        while (!que.isEmpty()) {
            int len = que.size();
            int maxNum = Integer.MIN_VALUE;
            while (len-- > 0) {
                TreeNode tempNode = que.poll();
                //maxNum = maxNum < tempNode.val ? tempNode.val : maxNum;
                maxNum=Math.max(maxNum,tempNode.val);
                if (tempNode.left != null) que.offer(tempNode.left);
                if (tempNode.right != null) que.offer(tempNode.right);
            }
            resList.add(maxNum);
        }
    }
}

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

指向下一个节点方法：

当前节点弹出后，它的next节点就是队列中的第一个元素，使用peek()即可查看下一个节点，注意处理每一层的最后一个节点即可。

            for (int i = 0; i < len; i++) {
        	...
                if (i < len - 1) {
                    tempNode.next = que.peek();
                } else {
                    tempNode.next = null;//最后一个节点让它指向null
                }
                ...
            }

为每一层最左边的节点虚构一个前节点即可在循环中将除最后一个节点的next填充，在循环外处理最后一个节点的next指针的指向即可。

       while (!que.isEmpty()) {
       		...
            Node pre = new Node();// 为每一层最左边的节点虚构一个前节点

            for (int i = 0; i < len; i++) {
            	...
                pre.next = tempNode; // 让左边的节点指向当前节点
                pre = tempNode; // 当前节点指定为下一个节点的左边节点
                ...
            }
            pre.next = null;//tempNode.next = null; // 让当前层的最后一个节点指向null
        }

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public Node connect(Node root) {
        Queue<Node> que = new LinkedList<>();
        if (root == null) {
            return null;
        }
        que.offer(root);
        while (!que.isEmpty()) {
            int len = que.size();
            Node pre = new Node();// 为每一层最左边的节点虚构一个前节点

            for (int i = 0; i < len; i++) {
                Node tempNode = que.poll();
                /*if (i < len - 1) {
                    tempNode.next = que.peek();
                } else {
                    //最后一个节点让它指向null
                    tempNode.next = null;
                }*/
                pre.next = tempNode; // 让左边的节点指向当前节点
                pre = tempNode; // 当前节点指定为下一个节点的左边节点
                if (tempNode.left != null) que.offer(tempNode.left);
                if (tempNode.right != null) que.offer(tempNode.right);
            }
            pre.next = null;//tempNode.next = null; // 让当前层的最后一个节点指向null
        }
        return root;
    }
}

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

这道题目说是二叉树，但 116题目说是完整二叉树，其实没有任何差别，一样的代码一样的逻辑一样的味道。（使用了虚拟左节点）

import java.util.Queue;

class Solution {
    public Node connect(Node root) {
        Queue<Node> que = new LinkedList<>();
        if (root == null) {
            return null;
        }
        que.offer(root);
        while (!que.isEmpty()) {
            int len = que.size();
            Node pre=new Node();// 为每一层最左边的节点虚构一个前节点

            for (int i = 0; i < len; i++) {
                Node tempNode = que.poll();
                pre.next=tempNode;// 让左边的节点指向当前节点
                pre=tempNode;// 当前节点指定为下一个节点的左边节点
                if(tempNode.left!=null)que.offer(tempNode.left);
                if(tempNode.right!=null)que.offer(tempNode.right);
            }
            pre.next=null;// 让当前层的最后一个节点指向null
        }
        return root;
    }
}

104.二叉树的最大深度

使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度。

import java.util.LinkedList;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        Queue<TreeNode> que = new LinkedList<>();
        if (root == null) {
            return 0;
        }
        que.offer(root);
        int deep = 0;
        while (!que.isEmpty()) {
            int len = que.size();
            deep++;// 记录深度
            while (len-- > 0) {
                TreeNode tempNode = que.poll();
                if(tempNode.left!=null)que.offer(tempNode.left);
                if(tempNode.right!=null)que.offer(tempNode.right);
            }
        }
        return deep;
    }
}

111.二叉树的最小深度

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

import java.util.LinkedList;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        Queue<TreeNode> que = new LinkedList<>();
        if (root == null) {
            return 0;
        }
        que.offer(root);
        int deep = 0;
        while (!que.isEmpty()) {
            int len = que.size();
            deep++;
            while (len-- > 0) {
                TreeNode tempNode = que.poll();
                //如果当前节点的左右孩子都为空，直接返回最小深度
                if (tempNode.left == null && tempNode.right == null) {
                   return deep;
                }
                if (tempNode.left != null) que.offer(tempNode.left);
                if (tempNode.right != null) que.offer(tempNode.right);
            }
        }
        return deep;
    }
}

226.翻转二叉树

①BFS层序遍历（广度优先遍历）

在遍历过程中交换左右节点。

import java.util.LinkedList;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        //层序遍历，在遍历过程中交换左右节点
        LinkedList<TreeNode> que=new LinkedList<TreeNode>();
        if(root==null){
            return null;
        }
        que.offer(root);
        while (!que.isEmpty()){
            int len = que.size();

            while(len-->0){
                TreeNode cur=que.poll();

                //交换左右节点
                TreeNode tempNode=cur.left;
                cur.left=cur.right;
                cur.right=tempNode;

                if(cur.left!=null){
                    que.offer(cur.left);
                }
                if(cur.right!=null){
                    que.offer(cur.right);
                }
            }
        }
        return root;
    }
}

②中序统一迭代遍历（模拟深度优先遍历，前中后都可）

递归法中序不行，但统一迭代遍历的中序可以，因为这是用栈来遍历，而不是靠指针来遍历，避免了递归法中翻转了两次的情况。

import java.util.LinkedList;
class Solution {
    public TreeNode invertTree(TreeNode root) {
        //中序迭代遍历
        LinkedList<TreeNode> stack = new LinkedList<>();
        if (root == null) {
            return null;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();
            if (node != null) {
                stack.pop();
                //（1）在压入栈之前就交换当前节点的左右子节点
                TreeNode tempNode = node.left;
                node.left = node.right;
                node.right = tempNode;
                if (node.right != null) stack.push(node.right);
                stack.push(node);
                stack.push(null);
                if (node.left != null) stack.push(node.left);
            } else {
                stack.pop();//弹出空指针
                stack.pop();//重新取出栈中元素
                //（2）节点处理逻辑 交换当前节点的左右子节点
                /*TreeNode tempNode = node.left;
                node.left = node.right;
                node.right = tempNode;*/
            }
        }
        return root;
    }
}

③DFS递归遍历（深度优先遍历，前序后序都可）

中序不行原因

前后序遍历都可以。中序不行，因为先左孩子交换孩子，再根交换孩子（做完后，右孩子已经变成了原来的左孩子），再右孩子交换孩子（此时其实是对原来的左孩子做交换）。
在这里插入图片描述
如果非要使用递归中序的方式写，也可以，如下代码就可以避免节点左右孩子翻转两次的情况：

//确定单层递归逻辑
        inorder(node.left);// 左
        TreeNode tempNode = node.left;// 中
        node.left = node.right;
        node.right = tempNode;
        inorder(node.left);// 注意 这里依然要遍历左孩子，因为中间节点已经翻转了

代码虽然可以，但这毕竟不是真正的递归中序遍历了。

前序（中节点需要交换左右子节点顺序，左右代表遍历方向）

//确定单层递归逻辑
        TreeNode tempNode = node.left;
        node.left = node.right;
        node.right = tempNode;
        preOrder(node.left);
        preOrder(node.right);

后序

//确定单层递归逻辑
        postorder(node.left);
        postorder(node.right);
        TreeNode tempNode = node.left;
        node.left = node.right;
        node.right = tempNode;

class Solution {
    public TreeNode invertTree(TreeNode root) {
        //DFS 递归前序遍历
        preOrder(root);
        return root;
    }

    public void preOrder(TreeNode node) {//确定递归参数和返回值
        //终止条件
        if (node == null) {
            return;
        }
        //确定单层递归逻辑
        TreeNode tempNode = node.left;
        node.left = node.right;
        node.right = tempNode;
        preOrder(node.left);
        preOrder(node.right);
    }
}