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

今日内容：

● 层序遍历*10

● 226.翻转二叉树

● 101.对称二叉树 2

详细布置

层序遍历

题目链接/文章讲解/视频讲解：https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html

思路：

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑

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

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

        return resList;
    }

    //DFS--递归方式
    public void checkFun01(TreeNode node, Integer deep) {
        if (node == null) {
            return;
        }
        deep++;
        if (resList.size() < deep) {
            //当层级增加时，list的Item也增加，利用list的索引值进行层级界定
            ArrayList<Integer> item = new ArrayList<>();
            resList.add(item);
        }
        resList.get(deep - 1).add(node.val);

        checkFun01(node.left, deep);
        checkFun01(node.right, deep);
    }

    //BFS--迭代方式--借助队列
    public void checkFun02(TreeNode node) {
        if (node == null) {
            return;
        }
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(node);

        while (!que.isEmpty()) {
            List<Integer> itemList = new ArrayList<>();
            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);
        }
    }
}
info
			解答成功:
			执行耗时:0 ms,击败了100.00% 的Java用户
			内存消耗:41.3 MB,击败了91.53% 的Java用户
info
			解答成功:
			执行耗时:1 ms,击败了61.26% 的Java用户
			内存消耗:41.5 MB,击败了57.26% 的Java用户

226.翻转二叉树 （优先掌握递归）

这道题目 一些做过的同学 理解的也不够深入，建议大家先看我的视频讲解，无论做过没做过，都会有很大收获。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0226.%E7%BF%BB%E8%BD%AC%E4%BA%8C%E5%8F%89%E6%A0%91.html

//DFS递归
class Solution {
    //递归函数的参数和返回值
    public TreeNode invertTree(TreeNode root) {
        //递归出口
        if (root == null) {
            return null;
        }
        invertTree(root.left);
        invertTree(root.right);
        swapChildren(root);
        return root;
    }
	//单层递归处理逻辑（交换左右结点）
    public void swapChildren(TreeNode root) {
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }
}

deque：操作

Queue 中 add() 和 offer()都是用来向队列添加一个元素。
在容量已满的情况下，add() 方法会抛出IllegalStateException异常，offer() 方法只会返回 false 。

poll（）方法 返回值：返回位于容器前面或队列开头的元素。当队列为空时，它返回null。

同时，Deque也可以作为LIFO(后进先出)堆栈,此接口优于传统的Stack类使用。

Stack和Deque方法的比较

Deque的使用场景
在一般情况，不涉及到并发的情况下，有两个实现类，可根据其自身的特性进行选择，分别是：

• LinkedList 大小可变的链表双端队列，允许元素为插入null。
• ArrayDeque 大下可变的数组双端队列，不允许插入null。
• ConcurrentLinkedDeque 大小可变且线程安全的链表双端队列，非阻塞，不允许插入null。
• LinkedBlockingDeque 为线程安全的双端队列，在队列为空的情况下，获取操作将会阻塞，直到有元素添加。

注意：LinkedList 和 ArrayDeque 是线程不安全的容器。

//BFS
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {return null;}
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            while (size-- > 0) {
                TreeNode node = deque.poll();
                swap(node);
                if (node.left != null) {deque.offer(node.left);}
                if (node.right != null) {deque.offer(node.right);}
            }
        }
        return root;
    }

    public void swap(TreeNode root) {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

101. 对称二叉树 （优先掌握递归）

先看视频讲解，会更容易一些。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0101.%E5%AF%B9%E7%A7%B0%E4%BA%8C%E5%8F%89%E6%A0%91.html

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

        private boolean compare(TreeNode left, TreeNode right) {
            if (left == null && right != null) {
                return false;
            }
            if (left != null && right == null) {
                return false;
            }
            if (left == null && right == null) {
                return true;
            }
            if (left.val != right.val) {
                return false;
            }
            // 比较外侧
            boolean compareOutside = compare(left.left, right.right);
            // 比较内侧
            boolean compareInside = compare(left.right, right.left);
            return compareOutside && compareInside;
        }
    }