代码随想录算法训练营第十三天-层序遍历、226翻转二叉树、101对称二叉树
初步题解
102 二叉树的层序遍历
题目链接：(https://leetcode.cn/problems/binary-tree-level-order-traversal/description/)
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| public List<List<Integer>> levelOrder(TreeNode root) {
ArrayList<List<Integer>> resultList = new ArrayList<>();
levelOrderDFS(root, 0, resultList);
levelOrderBFS(root, resultList);
return resultList;
}
private void levelOrderBFS(TreeNode root, ArrayList<List<Integer>> resultList) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
ArrayList<Integer> list = new ArrayList<>();
int size = queue.size();
while (size > 0) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
size--;
}
resultList.add(list);
}
}
private void levelOrderDFS(TreeNode root, int i, ArrayList<List<Integer>> resultList) {
if (root == null) {
return;
}
i++;
if (resultList.size() < i) {
ArrayList<Integer> list = new ArrayList<>();
resultList.add(list);
}
resultList.get(i - 1).add(root.val);
levelOrderDFS(root.left, i, resultList);
levelOrderDFS(root.right, i, resultList);
}
|
226 翻转二叉树
题目链接：(https://leetcode.cn/problems/invert-binary-tree/description/)
看了一部分的题目解析，突然反应过来 tree 不用自己构建，直接用方法简单很多。
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
|
public TreeNode invertTree(TreeNode root) {
invertTreePreorder(root);
return root;
}
private void invertTreePreorder(TreeNode root) {
if (root == null) {
return;
}
TreeNode temp = new TreeNode();
temp = root.left;
root.left = root.right;
root.right = temp;
if (root.left != null) {
invertTreePreorder(root.left);
}
if (root.right != null) {
invertTreePreorder(root.right);
}
}
|
101 对称二叉树
题目链接：(https://leetcode.cn/problems/symmetric-tree/description/)
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
public static boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
TreeNode right = root.right;
TreeNode left = root.left;
invertTreePreorder(left);
return isEqual(right, left);
}
private static boolean isEqual(TreeNode right, TreeNode left) {
if (right == null && left == null) {
return true;
}
if ((right == null && left != null) || (right != null && left == null)) {
return false;
}
if (right.val != left.val) {
return false;
}
return isEqual(right.right, left.right) && isEqual(right.left, left.left);
}
private static void invertTreePreorder(TreeNode root) {
if (root == null) {
return;
}
TreeNode temp;
temp = root.left;
root.left = root.right;
root.right = temp;
if (root.left != null) {
invertTreePreorder(root.left);
}
if (root.right != null) {
invertTreePreorder(root.right);
}
}
|
看解析
102 二叉树的层序遍历
题目链接/文章讲解/视频讲解：(https://programmercarl.com/0102.二叉树的层序遍历.html)
层序遍历一个二叉树。需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。
226 翻转二叉树
题目链接/文章讲解/视频讲解：(https://programmercarl.com/0226.翻转二叉树.html)
递归的中序遍历是不行的，因为使用递归的中序遍历，某些节点的左右孩子会翻转两次。
101 对称二叉树
题目链接/文章讲解/视频讲解：(https://programmercarl.com/0101.对称二叉树.html)
本题遍历只能是“后序遍历”，因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。
正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。
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
29
|
public static boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
TreeNode right = root.right;
TreeNode left = root.left;
return compare(right, left);
}
private static boolean compare(TreeNode right, TreeNode left) {
if (right == null && left == null) {
return true;
}
if ((right == null && left != null) || (right != null && left == null)) {
return false;
}
if (right.val != left.val) {
return false;
}
return compare(right.right, left.left) && compare(right.left, left.right);
}
|
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
public boolean isSymmetric2(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();
deque.offerFirst(root.left);
deque.offerLast(root.right);
while (!deque.isEmpty()) {
TreeNode leftNode = deque.pollFirst();
TreeNode rightNode = deque.pollLast();
if (leftNode == null && rightNode == null) {
continue;
}
if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
return false;
}
deque.offerFirst(leftNode.left);
deque.offerFirst(leftNode.right);
deque.offerLast(rightNode.right);
deque.offerLast(rightNode.left);
}
return true;
}
public boolean isSymmetric3(TreeNode root) {
Queue<TreeNode> deque = new LinkedList<>();
deque.offer(root.left);
deque.offer(root.right);
while (!deque.isEmpty()) {
TreeNode leftNode = deque.poll();
TreeNode rightNode = deque.poll();
if (leftNode == null && rightNode == null) {
continue;
}
if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
return false;
}
deque.offer(leftNode.left);
deque.offer(rightNode.right);
deque.offer(leftNode.right);
deque.offer(rightNode.left);
}
return true;
}
|