代码随想录算法训练营第十四天 | 翻转二叉树、对称二叉树、二叉树的最大深度、二叉树的最小深度
翻转二叉树
题目链接：https://leetcode.cn/problems/invert-binary-tree/description/
文章讲解：https://programmercarl.com/0226.翻转二叉树.html
视频讲解：https://www.bilibili.com/video/BV1sP4y1f7q7/?vd_source=b989f2b109eb3b17e8178154a7de7a51
采用层序遍历，遍历每个节点的时候将其左右子树交换
class Solution {public TreeNode invertTree(TreeNode root) {if(root == null){return root;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){int size = queue.size();while(size > 0){TreeNode curNode = queue.poll();TreeNode left = curNode.left;TreeNode right = curNode.right;curNode.left = right;curNode.right = left;if(left != null){queue.offer(left);}if(right != null){queue.offer(right);}size--;}}return root;}
}
这题也可以使用递归的方法做，这里采用前序遍历
class Solution {public TreeNode invertTree(TreeNode root){preOrder(root);return root;}public void preOrder(TreeNode root){if(root == null){return;}TreeNode left = root.left;root.left = root.right;root.right = left;preOrder(root.left);preOrder(root.right);}
}
对称二叉树
题目链接：https://leetcode.cn/problems/symmetric-tree/description/
文章讲解：https://programmercarl.com/0101.对称二叉树.html
视频讲解：https://www.bilibili.com/video/BV1ue4y1Y7Mf/?vd_source=b989f2b109eb3b17e8178154a7de7a51
采用后序遍历，递归法解决
- 左为空，右不为空，return false
- 左不为空，右为空，return false
- 左右都为空，return true
- 左右都不为空，但左右值不相等，return false
然后再递归比较外侧和内侧是否相等
class Solution {public boolean isSymmetric(TreeNode root) {return judge(root.left, root.right);}public boolean judge(TreeNode left, TreeNode right){if(left != null && right == null){return false;}else if(left == null && right != null){return false;}else if(left == null && right == null){return true;}else if(left.val != right.val){return false;}else{boolean outside = judge(left.left, right.right);boolean inside = judge(left.right, right.left);return outside && inside;}}
}
二叉树的最大深度
题目链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/
文章讲解：https://programmercarl.com/0104.二叉树的最大深度.html
视频讲解：https://www.bilibili.com/video/BV1Gd4y1V75u/?vd_source=b989f2b109eb3b17e8178154a7de7a51
二叉树节点的深度，指的是从根节点到该节点的最长简单路径边的条数或节点数（取决于深度从0开始还是从1开始）
二叉树节点的高度，指的是该节点到叶子节点的最长简单路径边的条数或节点数（取决于高度从0开始还是从1开始）
前序遍历（根左右）求的是深度，后序遍历（左右根）求的是高度，而根节点的高度其实就是二叉树的最大深度
class Solution {public int maxDepth(TreeNode root){if(root == null){return 0;}int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);int curHeight = 1 + Math.max(leftHeight, rightHeight);return curHeight;}
}
二叉树的最小深度
题目链接：https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/
文章讲解：https://programmercarl.com/0111.二叉树的最小深度.html
视频讲解：https://www.bilibili.com/video/BV1QD4y1B7e2/?vd_source=b989f2b109eb3b17e8178154a7de7a51
使用后序遍历，其实求的是根节点到叶子节点的最小距离，就是求高度的过程，不过这个最小距离也同样是最小深度
要注意的是，最小深度是从根节点到最近叶子节点的最短路径上的节点数量，注意是叶子节点，所以遇到左子树为空、右子树不为空，或者左子树不为空、右子树为空的情况，需要单独判断
class Solution {public int minDepth(TreeNode root){if(root == null){return 0;}int leftHeight = minDepth(root.left);int rightHeight = minDepth(root.right);if(root.left == null && root.right != null){return 1 + rightHeight;}else if(root.left != null && root.right == null){return 1 + leftHeight;}else{return 1 + Math.min(leftHeight, rightHeight);}}
}