剑指Offer(39):平衡二叉树
程序员文章站
2022-07-10 13:28:36
...
一、题目描述
输入一棵二叉树,判断该二叉树是否是平衡二叉树。
二、解题思路
使用后序遍历,遍历二叉树的每一个结点,在遍历某个结点之前已经遍历了它的左右子树,如果已经非平衡可以提前退出判断。
在遍历过程中,只需要记录每个结点的深度(深度等于它到叶结点的路径的长度),便可以在遍历的同时判断结点是否平衡。
例如:
[1]
[2] [3]
[4]
[5]
结点5左右子树深度差为0,返回它的深度max(0,0)+1=1
[1]
[2] [3]
[4]
[5]
结点4左右子树深度差为(1-0=1),返回它的深度max(1,0)+1=2
[1]
[2] [3]
[4]
[5]
结点2左右子树深度差为(2-0=2),超过1,返回-1,表明不平衡,退出递归
三、编程实现
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
return getDepth(root) != -1;
}
private int getDepth(TreeNode root) {
if (root == null) {
return 0;
}
// 左子树的深度
int left = getDepth(root.left);
// 如果左子树不平衡直接返回-1,表明该树不平衡
if (left == -1) {
return -1;
}
// 右子树的深度
int right = getDepth(root.right);
// 如果右子树不平衡直接返回-1,表明该树不平衡
if (right == -1) {
return -1;
}
// 如果左右子树深度差超过1,则返回-1,表明该树不平衡;
// 如果深度差小于等于1,则返回当前结点的深度
return Math.abs(left - right) > 1 ? -1 : (1 + Math.max(left, right));
}
}
推荐阅读
-
《剑指offer》面试题6 重建二叉树
-
剑指offer25:复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),结果返回复制后复杂链表的head。
-
剑指offer31:整数中1出现的次数(从1到n整数中1出现的次数)
-
剑指offer28:找出数组中超过一半的数字。
-
剑指offer27:按字典序打印出该字符串中字符的所有排列
-
C#版剑指Offer-001二维数组中的查找
-
剑指offer11:输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。(进制转换,补码反码)
-
剑指offer13:数组[奇数,偶数],奇数偶数相对位置不变。
-
剑指offer第二天
-
剑指offer JZ31 整数中1出现的次数 Python 解