共计 1467 个字符,预计需要花费 4 分钟才能阅读完成。
均衡二叉树
题目形容:给定一个二叉树,判断它是否是高度均衡的二叉树。
本题中,一棵高度均衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例阐明请见 LeetCode 官网。
起源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权,非商业转载请注明出处。
解法一:递归
- 首先,增加一个办法 height,该办法通过层序遍历的形式失去二叉树的高度。
而后,通过递归法判断二叉树是否是均衡二叉树,递归过程如下:
- 如果以后根节点为空,则间接返回 true;
- 否则,计算以后根节点的左右子树的高度,如果以后根节点的左右子树的高度之差不超过 1,则递归判断以后根节点的左右子树是否是均衡二叉树;否则,返回 false。
import com.kaesar.leetcode.TreeNode;
import java.util.LinkedList;
import java.util.Queue;
public class LeetCode_110 {
/**
* 递归
*
* @param root
* @return
*/
public static boolean isBalanced(TreeNode root) {
// 如果以后根节点为 null,必定是均衡的,间接返回 true
if (root == null) {return true;}
// 如果以后根节点的左右子树的高度之差不超过 1,则递归判断以后根节点的左右子树是否是均衡二叉树
if (height(root.left) - height(root.right) >= -1 && height(root.left) - height(root.right) <= 1) {return isBalanced(root.left) && isBalanced(root.right);
} else {return false;}
}
/**
* 层序遍历:通过计算二叉树的层数来失去二叉树的高度
*
* @param root 以后根节点
* @return 返回二叉树的高度
*/
public static int height(TreeNode root) {
int result = 0;
if (root == null) {return result;}
Queue<TreeNode> nodes = new LinkedList<>();
nodes.add(root);
result = 0;
while (!nodes.isEmpty()) {
result++;
int count = nodes.size();
while (count > 0) {TreeNode cur = nodes.poll();
if (cur.left != null) {nodes.add(cur.left);
}
if (cur.right != null) {nodes.add(cur.right);
}
count--;
}
}
return result;
}
public static void main(String[] args) {
// 测试用例,冀望返回后果:true
TreeNode root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
System.out.println(isBalanced(root));
}
}
【每日寄语】 把所有的不快给昨天,把所有的心愿给今天,把所有的致力给明天。
正文完