102.二叉树层序遍历
题目链接：102. 二叉树的层序遍历 - 力扣（LeetCode）题目
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1] 输出：[[1]]
示例 3：
输入：root = [] 输出：[]
思路
层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。
需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。
代码
1 // 102.二叉树的层序遍历
2 class Solution {
3 public List<List<Integer>> resList = new ArrayList<List<Integer>>();
4
5 public List<List<Integer>> levelOrder(TreeNode root) {
6 //checkFun01(root,0);
7 checkFun02(root);
8
9 return resList;
10 }
11
12 //DFS--递归方式
13 public void checkFun01(TreeNode node, Integer deep) {
14 if (node == null) return;
15 deep++;
16
17 if (resList.size() < deep) {
18 //当层级增加时，list的Item也增加，利用list的索引值进行层级界定
19 List<Integer> item = new ArrayList<Integer>();
20 resList.add(item);
21 }
22 resList.get(deep - 1).add(node.val);
23
24 checkFun01(node.left, deep);
25 checkFun01(node.right, deep);
26 }
27
28 //BFS--迭代方式--借助队列
29 public void checkFun02(TreeNode node) {
30 if (node == null) return;
31 Queue<TreeNode> que = new LinkedList<TreeNode>();
32 que.offer(node);
33
34 while (!que.isEmpty()) {
35 List<Integer> itemList = new ArrayList<Integer>();
36 int len = que.size();
37
38 while (len > 0) {
39 TreeNode tmpNode = que.poll();
40 itemList.add(tmpNode.val);
41
42 if (tmpNode.left != null) que.offer(tmpNode.left);
43 if (tmpNode.right != null) que.offer(tmpNode.right);
44 len--;
45 }
46
47 resList.add(itemList);
48 }
49
50 }
51 }
226.翻转二叉树
题目链接：226. 翻转二叉树 - 力扣（LeetCode）题目
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3] 输出：[2,3,1]
示例 3：
输入：root = [] 输出：[]
思路
想要翻转它，其实就把每一个节点的左右孩子交换一下就可以了。
关键在于遍历顺序，前中后序应该选哪一种遍历顺序？ （一些同学这道题都过了，但是不知道自己用的是什么顺序）
遍历的过程中去翻转每一个节点的左右孩子就可以达到整体翻转的效果。
注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果
这道题目使用前序遍历和后序遍历都可以，唯独中序遍历不方便，因为中序遍历会把某些节点的左右孩子翻转了两次！建议拿纸画一画，就理解了。
那么层序遍历可以不可以呢？依然可以的！只要把每一个节点的左右孩子翻转一下的遍历方式都是可以的！
代码
1 //DFS递归
2 class Solution {
3 /**
4 * 前后序遍历都可以
5 * 中序不行，因为先左孩子交换孩子，再根交换孩子（做完后，右孩子已经变成了原来的左孩子），再右孩子交换孩子（此时其实是对原来的左孩子做交换）
6 */
7 public TreeNode invertTree(TreeNode root) {
8 if (root == null) {
9 return null;
10 }
11 invertTree(root.left);
12 invertTree(root.right);
13 swapChildren(root);
14 return root;
15 }
16
17 private void swapChildren(TreeNode root) {
18 TreeNode tmp = root.left;
19 root.left = root.right;
20 root.right = tmp;
21 }
22 }
23
24 //BFS
25 class Solution {
26 public TreeNode invertTree(TreeNode root) {
27 if (root == null) {return null;}
28 ArrayDeque<TreeNode> deque = new ArrayDeque<>();
29 deque.offer(root);
30 while (!deque.isEmpty()) {
31 int size = deque.size();
32 while (size-- > 0) {
33 TreeNode node = deque.poll();
34 swap(node);
35 if (node.left != null) deque.offer(node.left);
36 if (node.right != null) deque.offer(node.right);
37 }
38 }
39 return root;
40 }
41
42 public void swap(TreeNode root) {
43 TreeNode temp = root.left;
44 root.left = root.right;
45 root.right = temp;
46 }
47 }
101.对称二叉树
题目链接：101. 对称二叉树 - 力扣（LeetCode）题目
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3] 输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3] 输出：false
思路
首先想清楚，判断对称二叉树要比较的是哪两个节点，要比较的可不是左右节点！
对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。
那么如何比较呢？
比较的是两个子树的里侧和外侧的元素是否相等。如图所示：
那么遍历的顺序应该是什么样的呢？
本题遍历只能是“后序遍历”，因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。
正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。
但都可以理解算是后序遍历，尽管已经不是严格上在一个树上进行遍历的后序遍历了。
其实后序也可以理解为是一种回溯，当然这是题外话，讲回溯的时候会重点讲的。
说到这大家可能感觉我有点啰嗦，哪有这么多道理，上来就干就完事了。别急，我说的这些在下面的代码讲解中都有身影。
那么我们先来看看递归法的代码应该怎么写。
代码
递归法
递归三部曲
- 确定递归函数的参数和返回值
因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。
返回值自然是
boolean 类型。
代码如下：
1 private boolean compare(TreeNode left, TreeNode right)
- 确定终止条件
要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！否则后面比较数值的时候就会操作空指针了。
节点为空的情况有：（注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点）
- 左节点为空，右节点不为空，不对称，return false
- 左不为空，右为空，不对称 return false
- 左右都为空，对称，返回true
此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：
- 左右都不为空，比较节点数值，不相同就return false
此时左右节点不为空，且数值也不相同的情况我们也处理了。
代码如下：
1 if (left == null && right != null) {
2 return false;
3 }
4 if (left != null && right == null) {
5 return false;
6 }
7
8 if (left == null && right == null) {
9 return true;
10 }
11 if (left.val != right.val) {
12 return false;
13 }
- 确定单层递归的逻辑
此时才进入单层递归的逻辑，单层递归的逻辑就是处理 左右节点都不为空，且数值相同的情况。
- 比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
- 比较内测是否对称，传入左节点的右孩子，右节点的左孩子。
- 如果左右都对称就返回true ，有一侧不对称就返回false 。
代码如下：
1 // 比较外侧 2 boolean compareOutside = compare(left.left, right.right); 3 // 比较内侧 4 boolean compareInside = compare(left.right, right.left); 5 return compareOutside && compareInside;
如上代码中，我们可以看出使用的遍历方式，左子树左右中，右子树右左中，所以我把这个遍历顺序也称之为“后序遍历”（尽管不是严格的后序遍历）。
完整代码
1 public boolean isSymmetric1(TreeNode root) {
2 return compare(root.left, root.right);
3 }
4
5 private boolean compare(TreeNode left, TreeNode right) {
6
7 if (left == null && right != null) {
8 return false;
9 }
10 if (left != null && right == null) {
11 return false;
12 }
13
14 if (left == null && right == null) {
15 return true;
16 }
17 if (left.val != right.val) {
18 return false;
19 }
20 // 比较外侧
21 boolean compareOutside = compare(left.left, right.right);
22 // 比较内侧
23 boolean compareInside = compare(left.right, right.left);
24 return compareOutside && compareInside;
25 }
迭代法
1 /**
2 * 迭代法
3 * 使用双端队列，相当于两个栈
4 */
5 public boolean isSymmetric2(TreeNode root) {
6 Deque<TreeNode> deque = new LinkedList<>();
7 deque.offerFirst(root.left);
8 deque.offerLast(root.right);
9 while (!deque.isEmpty()) {
10 TreeNode leftNode = deque.pollFirst();
11 TreeNode rightNode = deque.pollLast();
12 if (leftNode == null && rightNode == null) {
13 continue;
14 }
15 // if (leftNode == null && rightNode != null) {
16 // return false;
17 // }
18 // if (leftNode != null && rightNode == null) {
19 // return false;
20 // }
21 // if (leftNode.val != rightNode.val) {
22 // return false;
23 // }
24 // 以上三个判断条件合并，注意，在上面已经帮我们筛选掉左右节点都不为空的情况，所以接下可直接判断左右节点中哪一个节点为空，避免空指针异常
25 if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
26 return false;
27 }
28 deque.offerFirst(leftNode.left);
29 deque.offerFirst(leftNode.right);
30 deque.offerLast(rightNode.right);
31 deque.offerLast(rightNode.left);
32 }
33 return true;
34 }
35
36 /**
37 * 迭代法
38 * 使用普通队列
39 */
40 public boolean isSymmetric3(TreeNode root) {
41 Queue<TreeNode> deque = new LinkedList<>();
42 deque.offer(root.left);
43 deque.offer(root.right);
44 while (!deque.isEmpty()) {
45 TreeNode leftNode = deque.poll();
46 TreeNode rightNode = deque.poll();
47 if (leftNode == null && rightNode == null) {
48 continue;
49 }
50 // if (leftNode == null && rightNode != null) {
51 // return false;
52 // }
53 // if (leftNode != null && rightNode == null) {
54 // return false;
55 // }
56 // if (leftNode.val != rightNode.val) {
57 // return false;
58 // }
59 // 以上三个判断条件合并
60 if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
61 return false;
62 }
63 // 这里顺序与使用Deque不同
64 deque.offer(leftNode.left);
65 deque.offer(rightNode.right);
66 deque.offer(leftNode.right);
67 deque.offer(rightNode.left);
68 }
69 return true;
70 }
标签：right,return,层序,随想录,遍历,二叉树,null,root,left From： https://www.cnblogs.com/xpp3/p/17125319.html