• 欢迎光临~

# 代码随想录训练营｜Day 15｜102, 226, 101

### 102. Binary Tree Level Order Traversal

Given the `root` of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example 1:

``````Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
``````

Example 2:

``````Input: root = [1]
Output: [[1]]
``````

Example 3:

``````Input: root = []
Output: []
``````

Constraints:

• The number of nodes in the tree is in the range `[0, 2000]`.
• `1000 <= Node.val <= 1000`

102.二叉树的层序遍历
107.二叉树的层次遍历II
199.二叉树的右视图
637.二叉树的层平均值
429.N叉树的层序遍历
515.在每个树行中找最大值
116.填充每个节点的下一个右侧节点指针
117.填充每个节点的下一个右侧节点指针II
104.二叉树的最大深度
111.二叉树的最小深度

``````class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) return ans;
Deque<TreeNode> queue = new ArrayDeque<>();
while (!queue.isEmpty()) {
int qlen = queue.size();
List<Integer> row = new ArrayList<>();
for (int i = 0; i < qlen; i++) {
TreeNode curr = queue.poll();
}
}
return ans;
}
}
``````

Time Complexity：O(n)
Space Complexity：O(n)

For Future References

### 226. Invert Binary Tree

Given the `root` of a binary tree, invert the tree, and return its root.

Example 1:

``````Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

``````

Example 2:

``````Input: root = [2,1,3]
Output: [2,3,1]
``````

Example 3:

``````Input: root = []
Output: []
``````

Constraints:

• The number of nodes in the tree is in the range `[0, 100]`.
• `100 <= Node.val <= 100`

DFS

``````class Solution {
/**
* 前后序遍历都可以
* 中序不行，因为先左孩子交换孩子，再根交换孩子（做完后，右孩子已经变成了原来的左孩子），再右孩子交换孩子（此时其实是对原来的左孩子做交换）
*/
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
invertTree(root.left);
invertTree(root.right);
swapChildren(root);
return root;
}

private void swapChildren(TreeNode root) {
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
}
}
``````

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;
}
}
``````

Time Complexity：O(n)
Space Complexity：O(n)

For Future References

### 101. Symmetric Tree

Given the `root` of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

``````Input: root = [1,2,2,3,4,4,3]
Output: true
``````

Example 2:

``````Input: root = [1,2,2,null,3,null,3]
Output: false
``````

Constraints:

• The number of nodes in the tree is in the range `[1, 1000]`.
• `100 <= Node.val <= 100`

Could you solve it both recursively and iteratively?

• 左节点为空，右节点不为空，不对称，return false
• 左不为空，右为空，不对称 return false
• 左右都为空，对称，返回true

• 左右都不为空，比较节点数值，不相同就return false

``````public boolean isSymmetric1(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;
}
``````

Time Complexity：O(n)
Space Complexity：O(n)

For Future References