110. 平衡二叉树
LeetCode题目要求
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
![图](/i/l/?n=23&i=blog/458364/202301/458364-20230123170253069-1855524107.png)
示例
输入:root = [3,9,20,null,null,15,7]
输出:true
解题思路
本题要判断的是节点的高度,高度是指:从该节点到叶子节点的最长简单路径边的条数。(按LeetCode要求是从节点计算的)。如下图:
![图](/i/l/?n=23&i=blog/458364/202301/458364-20230123170816588-1729005094.png)
而计算节点的高度,我们要使用后序遍历,即左右中,这样可计算出节点的高度。
上代码,递归法
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
// 分别计算 左右子树的高度,如果出现高度相差超过 1,就返回 false
return getHeight(root) != -1;
}
public int getHeight(TreeNode node) {
// 节点为空时,说明没有节点,那么高度也就是 0 了
if (node == null) {
return 0;
}
// 计算左子树高度,递归计算
int leftHeight = getHeight(node.left);
if (leftHeight == -1) {
return -1;
}
// 计算右子树高度,递归计算
int rightHeight = getHeight(node.right);
if (rightHeight == -1) {
return -1;
}
// 左右子树高度差结果 > 1 说明不是平衡二叉树,那么返回 -1
if (Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}
// + 上父结点,计算节点高度,这里计算一个子树的高度,需要的是左或右为最高的那个
return 1 + Math.max(leftHeight, rightHeight);
}
}
重难点
需要重点理解的是用后序遍历来计算节点高度
附:学习资料链接
标签:return,17,高度,Day,二叉树,计算,leftHeight,节点 From: https://www.cnblogs.com/blacksonny/p/17065313.html