目录
226. 翻转二叉树
题目描述
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
做题思路
本题属于二叉树的基础题目，需要牢牢掌握。
参考代码
//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;
}
}
101. 对称二叉树
题目描述
给你一个二叉树的根节点 root ， 检查它是否轴对称。
做题思路
本题属于二叉树的基础题目，需要牢牢掌握。
参考代码
/**
* 递归法
*/
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;
}
/**
* 迭代法
* 使用双端队列，相当于两个栈
*/
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) {
// return false;
// }
// if (leftNode != null && rightNode == null) {
// return false;
// }
// if (leftNode.val != rightNode.val) {
// return false;
// }
// 以上三个判断条件合并
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) {
// return false;
// }
// if (leftNode != null && rightNode == null) {
// return false;
// }
// if (leftNode.val != rightNode.val) {
// return false;
// }
// 以上三个判断条件合并
if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
return false;
}
// 这里顺序与使用Deque不同
deque.offer(leftNode.left);
deque.offer(rightNode.right);
deque.offer(leftNode.right);
deque.offer(rightNode.left);
}
return true;
}
104.二叉树的最大深度
题目描述
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3
示例 2：
输入：root = [1,null,2]
输出：2
提示：
- 树中节点的数量在
[0, 104]区间内。 -100 <= Node.val <= 100
参考代码
class solution {
/**
* 递归法
*/
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}
111.二叉树的最小深度
题目描述
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
**说明：**叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
提示：
- 树中节点数的范围在
[0, 105]内 -1000 <= Node.val <= 1000
参考代码
class Solution {
/**
* 递归法，相比求MaxDepth要复杂点
* 因为最小深度是从根节点到最近**叶子节点**的最短路径上的节点数量
*/
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
if (root.left == null) {
return rightDepth + 1;
}
if (root.right == null) {
return leftDepth + 1;
}
// 左右结点都不为null
return Math.min(leftDepth, rightDepth) + 1;
}
}
