文章目录
day15学习内容
day15主要内容
- 二叉树的层序遍历
- 翻转二叉树
- 对称二叉树,其实就是判断2个树能不能翻转。
声明
本文思路和文字,引用自《代码随想录》
一、二叉树的层序遍历
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.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;
}
}
二、翻转二叉树
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;
}
}
三、对称二叉树
核心思路:比较根节点的两个子树是否是相互翻转的
2.1、怎么判断是否可以翻转
所谓是否可以翻转,就是判断左子树的左侧节点和右子树的右节点是否值相等,如果存在且值相等,就认为是可以翻转的。
也就是外侧和外侧相比,内侧和内侧相比。
2.2、思路
本题采用递归实现,所以想一下递归三部曲的思路,
- 确定返回值和参数
- 返回值肯定是树
- 参数:因为要翻转,所以要把左子树和右子树传入
- 确定递归终止条件
- 递归结束条件比较多,
- 1、左子树为空,右子树不为空,肯定不能翻转
- 2、左子树不为空,右子树为空,肯定不能翻转
- 3、左右子树都为空,可以翻转
- 4、左右子树都不为空,且值不相等,肯定不能翻转
- 5、左右子树都不为空,且值相等,需要继续递归判断能否翻转。
- 确定单层递归逻辑,也就是如何向下一层遍历
- 按照上面分析,判断能不能翻转就是要2种情况
- 判断左子树的左节点和右子树的右节点是否值相等(比较好理解,想象一下镜像就行)
- 断左子树的右节点和右子树的左节点是否值相等(比较好理解,想象一下镜像就行)
- 按照上面分析,判断能不能翻转就是要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.思维导图
本文思路引用自代码随想录,感谢代码随想录作者。