判断是否为平衡二叉树
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 52 ms, 内存: 19.7 MB
// 思路:
// 使用Java Stream API来处理树的遍历和深度计算。
// 然而,由于Java Stream API不太适合处理递归,因此我们还是使用递归的方法计算深度。
// 这里展示的代码和普通的Java代码相似,因为Stream API不适合树的递归遍历。
class Solution {
public boolean isBalanced(TreeNode root) {
return depth(root) != -1;
}
private int depth(TreeNode node) {
if (node == null) return 0;
int leftDepth = depth(node.left);
if (leftDepth == -1) return -1;
int rightDepth = depth(node.right);
if (rightDepth == -1) return -1;
if (Math.abs(leftDepth - rightDepth) > 1) return -1;
return Math.max(leftDepth, rightDepth) + 1;
}
}
解释
方法:
这个题解采用了递归的方式来判断一棵二叉树是否是平衡的。平衡二叉树的定义是,任意节点的左右子树的深度相差不超过1。题解中定义了一个辅助函数 helper,这个函数递归地计算树的高度,同时检查是否满足平衡条件。如果子树是平衡的,返回其高度;如果发现不平衡,则返回-1作为标记。主函数通过检查 helper 的返回值是否为 -1 来判断整棵树是否平衡。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在递归函数中返回-1是如何有效地标识子树不平衡的,这种方法是否可能与其他树的高度计算混淆?
▷🦆
递归检查每个节点的左右子树高度差时,是否存在重复计算问题?如果存在,如何优化以提高效率?
▷🦆
函数helper在遇到不平衡的情况时立即返回-1,这种提前退出的策略对算法性能有何影响?
▷