Leetcode上的前120道题的简单题已经几乎做完了，递归数据类型的题还是遇到不少。递归是一种比较优雅的解题方法，奈何我并不能每次都很顺利地写出递归解法，所以在这里做一个Leetcode前120道简单题之二叉树问题递归解法总结。
100.相同的数
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
/**定义二叉树类，后同，省略
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
//结束标志：两个树均为空
if(p == null && q == null){
return true;
}
//两树均不为空且值相同
if(p != null && q != null && p.val == q.val){
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}else{
return false;
}
}
}
101.对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
class Solution {
//结束标志：根节点为空，或者根节点的只有左子树或右子树
public boolean isSymmetric(TreeNode root) {
if(root == null){
return true;
}
if((root.left == null && root.right != null)||(root.left != null && root.right == null)){
return false;
}
return isSymmetricChild(root.left, root.right);
}
//对称的情况：左右叶子节点均为空；左右叶子节点的值相同（则将子节点的左右子树作为输入再次迭代）
private boolean isSymmetricChild(TreeNode left, TreeNode right){
if(left == null && right == null){
return true;
}
if((left == null && right != null)||(right == null && left != null)){
return false;
}
if(left.val == right.val){
return isSymmetricChild(left.left,right.right) && isSymmetricChild(right.left,left.right);
}
else{
return false;
}
}
}
104.二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
class Solution {
public int maxDepth(TreeNode root) {
//结束标志：根节点为空
if(root == null){
return 0;
};
//左右子树的最大深度，+1
int left = maxDepth(root.left) + 1;
int right = maxDepth(root.right) + 1;
int max = Math.max(left, right);
//返回子树最大深度的最大值
return max;
}
}
108.将有序数组转化成二叉搜索树
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例：
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
class Solution {
//结束标志：待转化的数组为空
public TreeNode sortedArrayToBST(int[] nums) {
return nums == null ? null : buildTree(nums, 0, nums.length - 1);
}
private TreeNode buildTree(int[] nums, int l , int r){
if(l > r){
return null;
}
//找到数组中点作为根节点
int m = l + (r - l) / 2;
TreeNode root = new TreeNode(nums[m]);
//左右子树分别建立二叉树
root.left = buildTree(nums, l , m - 1);
root.right = buildTree(nums, m + 1, r);
//返回根节点
return root;
}
}
110.平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
class Solution {
public boolean isBalanced(TreeNode root) {
return isBST(root).isB;
}
private class ReturnNode {
boolean isB;
int depth;
public ReturnNode(boolean isB, int depth){
this.isB = isB;
this.depth = depth;
}
}
//结束标志：根节点为空
public ReturnNode isBST(TreeNode root) {
if(root == null) {
return new ReturnNode(true, 0);
}
//不平衡的三种情况：左数不平衡， 右数不平衡 ，左右树深度差值大于1
ReturnNode left = isBST(root.left);
ReturnNode right = isBST(root.right);
if(left.isB == false || right.isB == false) {
return new ReturnNode(false, 0);
}
if(Math.abs(left.depth - right.depth) > 1) {
return new ReturnNode(false, 0);
}
//返回左右子树的最大深度，+1
return new ReturnNode(true, Math.max(left.depth, right.depth) + 1);
}
}
111.二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
class Solution {
public int minDepth(TreeNode root) {
//结束标志：根节点为空
if(root == null){
return 0;
}
if(root.left == null && root.right == null) {
return 1;
}
//左右子树的最小深度，+1
int a = minDepth(root.left) + 1;
a = (a==1 ? Integer.MAX_VALUE : a);
int b = minDepth(root.right) + 1;
b = (b==1 ? Integer.MAX_VALUE : b);
int min = Math.min(a, b);//
//返回子树中的最小深度
return min;
}
}
小结：其实递归解法的代码是有一定的规律的，主要需要注意三个地方：
- 递归结束的标志
- 单层递归中需要做的事情
- 每层递归给下一层传的返回值。
更新：好久没做，又有点忘了怎么写递归的程序了，补充一道2019/10/23做的题。
226.翻转二叉树
翻转一棵二叉树。
class Solution {
public TreeNode invertTree(TreeNode root) {
//结束标识：节点为空
if (root == null) {
return root;
} else {
//交换操作
TreeNode node = root.right;
root.right = root.left;
root.left = node;
root.right = invertTree(root.right);
root.left = invertTree(root.left);
}
return root;
}
}
网友评论