文章目录
1、题目描述2、解题思路2.1 自上向下的方法2.2 自下向上的方法
3、解题代码3.1 自上向下的方法3.2 自下向上的方法
4、解题心得
1、题目描述
【JZ39】输入一棵二叉树，判断该二叉树是否是平衡二叉树。在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树。 知识点：树，递归 难度：☆
2、解题思路
平衡二叉树的特点：它是一棵空树或它的左右两颗子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 根据平衡二叉树的特点，只需要做好两个判断就行： 1、左右子树的高度差的绝对值是否超过1？ 2、左右子树是否平衡二叉树？ 第一个判断涉及到二叉树的高度计算，可以参考我的第三篇博客https://blog.csdn.net/qq_29051413/article/details/106806105 第二个判断是否平衡二叉树可以采用递归的思想。
2.1 自上向下的方法
从根结点开始，先判断左右子树的高度差是否小于等于1，如果是，则继续判断左右子树是否平衡二叉树。
2.2 自下向上的方法
我们可以在计算二叉树高度时增加一个标记flag，从叶子结点开始往上遍历，当某个结点的左子树和右子树高度差大于1时，返回当前结点的高度为-1，表示告诉父节点不用计算高度了，因为已经不满足平衡二叉树的条件了。（一颗老鼠屎坏了一锅粥）
3、解题代码
3.1 自上向下的方法
package pers
.klb
.jzoffer
.medium
;
public class BalancedBinaryTree {
public boolean IsBalanced_Solution(TreeNode root
) {
return judge(root
);
}
private boolean judge(TreeNode root
) {
if (root
== null
) {
return true;
}
return Math
.abs(TreeDepth(root
.left
) - TreeDepth(root
.right
)) <= 1 &&
judge(root
.left
) &&
judge(root
.right
);
}
private int TreeDepth(TreeNode root
) {
if (root
== null
) {
return 0;
}
int leftDepth
= 0;
int rightDepth
= 0;
if (root
.left
!= null
) {
leftDepth
= TreeDepth(root
.left
);
}
if (root
.right
!= null
) {
rightDepth
= TreeDepth(root
.right
);
}
return Math
.max(leftDepth
, rightDepth
) + 1;
}
}
class TreeNode {
public int val
= 0;
public TreeNode left
= null
;
public TreeNode right
= null
;
public TreeNode(int val
) {
this.val
= val
;
}
}
时间复杂度：O(N) 空间复杂度：O(N)
3.2 自下向上的方法
package pers
.klb
.jzoffer
.medium
;
public class BalancedBinaryTree {
public boolean IsBalanced_Solution(TreeNode root
) {
return TreeDepth(root
) != -1;
}
private int TreeDepth(TreeNode root
) {
if (root
== null
) {
return 0;
} else {
int leftDepth
= TreeDepth(root
.left
);
if (leftDepth
== -1) return -1;
int rightDepth
= TreeDepth(root
.right
);
if (rightDepth
== -1) return -1;
int sub
= Math
.abs(rightDepth
- leftDepth
);
if (sub
> 1) return -1;
return Math
.max(rightDepth
, leftDepth
) + 1;
}
}
}
class TreeNode {
public int val
= 0;
public TreeNode left
= null
;
public TreeNode right
= null
;
public TreeNode(int val
) {
this.val
= val
;
}
}
4、解题心得
