leetcode 226. 翻转二叉树
题目描述
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
解题思路
逐层交换左右子节点
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null ) return root;
if (root.left == null && root.right == null) return root;
TreeNode node = root.left;
root.left = root.right;
root.right = node;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
// 迭代法
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null) return root;
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while(!que.isEmpty()){
int len = que.size();
while(len-- > 0){
TreeNode node = que.poll();
if(node.left != null){
que.offer(node.left);
}
if(node.right != null){
que.offer(node.right);
}
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
}
}
return root;
}
}
leetcode 101. 对称二叉树
题目描述
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例
输入：root = [1,2,2,3,4,4,3]
输出：true
解题思路
- 根节点不参与比较
- 按照 中 - 外 - 内的顺序比较
class Solution {
public boolean isSymmetric(TreeNode root) {
return compare(root.left, root.right);
}
public 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;
}
return compare(left.left, right.right) && compare(left.right, right.left);
}
}
// 迭代法，使用双端队列，左子树的从队首插入，右子树的从队尾插入
class Solution {
public boolean isSymmetric(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();
deque.offerFirst(root.left);
deque.offerLast(root.right);
while(!deque.isEmpty()){
TreeNode left = deque.pollFirst();
TreeNode right = deque.pollLast();
if(left == null && right == null){
continue;
}
if(left == null || right == null || left.val != right.val)
return false;
// 顺序不能变
deque.offerFirst(left.right);
deque.offerFirst(left.left);
deque.offerLast(right.left);
deque.offerLast(right.right);
}
return true;
}
LeetCode 104.二叉树的最大深度
题目描述
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数
示例
输入：root = [3,9,20,null,null,15,7]
输出：3
题目链接
https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/
解题思路
层序遍历, 增加 depth记录层数
class Solution {
public int maxDepth(TreeNode root) {
int res = 0;
Queue<TreeNode> que = new LinkedList<>();
if (root != null) que.offer(root);
while (!que.isEmpty()) {
int len = que.size();
while (len-- > 0) {
TreeNode node =que.poll();
if (node.left != null) que.offer(node.left);
if (node.right != null) que.offer(node.right);
}
res++;
}
return res;
}
}
LeetCode 111.二叉树的最小深度
题目描述
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
**说明：**叶子节点是指没有子节点的节点。
示例
输入：root = [3,9,20,null,null,15,7]
输出：2
题目链接
https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/
解题思路
层序遍历, 只有当左右节点都为空时, 返回深度
class Solution {
public int minDepth(TreeNode root) {
int res = 0;
Queue<TreeNode> que = new LinkedList<>();
if (root != null ) que.offer(root);
while (!que.isEmpty()) {
int len = que.size();
res++;
while (len-- > 0) {
TreeNode node = que.poll();
if (node.left == null && node.right == null) return res;
if (node.left != null) que.offer(node.left);
if (node.right != null) que.offer(node.right);
}
}
return res;
}
}
递归法
class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;
}
}
评论