leetcode
leetcode 2601 ~ 2650
判断是否为平衡二叉树

判断是否为平衡二叉树

难度:

标签:

题目描述

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是如何有效地标识子树不平衡的,这种方法是否可能与其他树的高度计算混淆?
在递归函数中,返回-1用于有效地标识子树不平衡。这种方法的设计是基于高度计算的一个特殊约定,即正常树的高度非负(空树为0,非空树至少为1)。因此,-1作为一个负值,不会与任何有效的树高度混淆,从而可以明确标识出不平衡状态。此外,一旦返回-1,上层递归调用会继续传递这个值,避免进一步的无用计算。
🦆
递归检查每个节点的左右子树高度差时,是否存在重复计算问题?如果存在,如何优化以提高效率?
在原始的递归实现中,每个节点的左右子树的高度会被计算一次,且这些高度值在父节点中被用来计算平衡状态和高度。虽然每个节点的高度计算本身不重复,但在整体的递归过程中,每个节点都被访问一次来计算其高度。优化的方法是使用后序遍历的方式,即在返回节点高度的同时,一并返回该节点是否平衡的信息,从而避免重复的状态检查和高度计算。具体来说,可以设计一个辅助函数,返回一个包含两个元素的元组,第一个元素表示高度,第二个元素表示是否平衡,这样可以在每个节点仅进行一次计算的基础上完成整个树的判断。
🦆
函数helper在遇到不平衡的情况时立即返回-1,这种提前退出的策略对算法性能有何影响?
函数helper在发现不平衡的情况时立即返回-1,这种提前退出的策略大幅提高了算法性能。这样做避免了对整棵树的全面遍历,尤其是在树的某个部分早早地发现不平衡时,可以省去对其他部分的无效计算。这种策略使得算法的时间复杂度在最佳情况下大幅降低,尤其是在不平衡迅速被检测到的情况下。这种策略是一种典型的剪枝操作,有效减少了递归调用的数量和深度。

相关问题