110. 平衡二叉树
问题描述
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
解题思路 1
首先,计算左右子树的最大深度,如果左右子树的高度差是否不超过 1,则该节点的左右子树高度平衡;
然后,再分别递归地遍历左右子节点,分别判断除根节点外的每个节点的左子树和右子树是否平衡。
代码实现 1
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
return Math.abs(getDepth(root.left) - getDepth(root.right)) > 1 ? false : true
&& isBalanced(root.left) && isBalanced(root.right);
}
public int getDepth(TreeNode root){
if(root == null){
return 0;
}
int leftDepth = getDepth(root.left);
int rightDepth = getDepth(root.right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
}
解题思路 2
上一种方法中计算二叉树深度的函数会被重复调用。其实,在计算二叉树深度时即可以判断节点的左右子树是否平衡。定义返回值-1,用以标识节点的左右子树不是高度平衡的。只有有任意一个节点的左右子树不是高度平衡的,则可以判定整个二叉树不是高度平衡的。
代码实现2
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
return getDepth(root) >= 0;
}
public int getDepth(TreeNode root){
if(root == null){
return 0;
}
int leftDepth = getDepth(root.left);
if(leftDepth == -1 ){
return -1;
}
int rightDepth = getDepth(root.right);
if(rightDepth == -1 ){
return -1;
}
return Math.abs(leftDepth - rightDepth) > 1 ? -1 : Math.max(leftDepth, rightDepth) + 1;
}
}
111. 二叉树的最小深度
问题描述
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。
解题思路
递归求出左右子树的最小深度,然后返回较小的值。
注意:当左/右子树二者有且仅有一者为空时,空子树的minDepth为0。但由于空子树没有叶子节点,所以即使0是较小的值,也应该返回非空子树的minDepth。
代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if(root == null){
return 0;
}
if(root.left == null && root.right == null){
return 1;
}
int left = minDepth(root.left);
int right = minDepth(root.right);
if(left == 0){
//左子树为空
return right + 1;
}else if(right == 0){
//右子树为空
return left + 1;
}else{
//左、右子树均不为空
return left < right ? left + 1 : right + 1;
}
}
}