代码随想录刷题day15｜二叉树的层序遍历&翻转二叉树&对称二叉树

---

day15学习内容

day15主要内容

• 二叉树的层序遍历
• 翻转二叉树
• 对称二叉树，其实就是判断2个树能不能翻转。

---

声明
本文思路和文字，引用自《代码随想录》

一、二叉树的层序遍历

102.原题链接

1.1、思路

• 从根节点开始遍历树，把每一层的节点放入到队列中。

1.2、错误写法

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        if (root == null) {
            return result;
        }
        deque.offer(root);
        while (root!=null) {
            List<Integer> itemList = new ArrayList<>();
            int size = deque.size();
            while (size > 0) {
                TreeNode tmpNode = deque.poll();
                itemList.add(tmpNode.val);
                if (tmpNode.left != null) {
                    deque.offer(tmpNode.left);
                }
                if (tmpNode.right != null) {
                    deque.offer(tmpNode.right);
                }
                size--;
            }
            result.add(itemList);
        }

        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

为什么这么写是错的。
很明显，能写出这种代码说明没有理解思路。没有理解怎么保存当前层的节点个数。

1.3、正确写法

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        if (root == null) {
            return result;
        }
        deque.offer(root);
        while (!deque.isEmpty()) {
            List<Integer> itemList = new ArrayList<>();
            int size = deque.size();
            while (size > 0) {
                TreeNode tmpNode = deque.poll();
                itemList.add(tmpNode.val);
                if (tmpNode.left != null) {
                    deque.offer(tmpNode.left);
                }
                if (tmpNode.right != null) {
                    deque.offer(tmpNode.right);
                }
                size--;
            }
            result.add(itemList);
        }

        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

二、翻转二叉树

226.原题链接

2.1、思路

• 使用递归实现翻转
• 比较简单的一题吧

2.2、正确写法

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        swapChirdren(root);
        invertTree(root.left);
        invertTree(root.right);
        return root;

    }

    private TreeNode swapChirdren(TreeNode root) {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

三、对称二叉树

101.原题链接

核心思路：比较根节点的两个子树是否是相互翻转的

2.1、怎么判断是否可以翻转

所谓是否可以翻转，就是判断左子树的左侧节点和右子树的右节点是否值相等，如果存在且值相等，就认为是可以翻转的。
也就是外侧和外侧相比，内侧和内侧相比。

2.2、思路

本题采用递归实现，所以想一下递归三部曲的思路，

• 确定返回值和参数
  • 返回值肯定是树
  • 参数：因为要翻转，所以要把左子树和右子树传入
• 确定递归终止条件
  • 递归结束条件比较多，
  • 1、左子树为空，右子树不为空，肯定不能翻转
  • 2、左子树不为空，右子树为空，肯定不能翻转
  • 3、左右子树都为空，可以翻转
  • 4、左右子树都不为空，且值不相等，肯定不能翻转
  • 5、左右子树都不为空，且值相等，需要继续递归判断能否翻转。
• 确定单层递归逻辑，也就是如何向下一层遍历
  • 按照上面分析，判断能不能翻转就是要2种情况
    • 判断左子树的左节点和右子树的右节点是否值相等(比较好理解，想象一下镜像就行)
    • 断左子树的右节点和右子树的左节点是否值相等(比较好理解，想象一下镜像就行)

2.3、正确代码

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 b1 = compare(left.left, right.right);
        boolean b2 = compare(left.right, right.left);
        //内侧和外侧的结果需要告诉上一层的父节点，
        return b1 && b2;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

总结

1.感想

• 比较顺利的一天，对称二叉树要好好想一下思路。

2.思维导图

本文思路引用自代码随想录，感谢代码随想录作者。