共翁号
共翁号 > 知识 > 判断二叉树是否为平衡二叉树

判断二叉树是否为平衡二叉树

原创2025-06-21 01:00:50

要判断一个二叉树是否是平衡二叉树,可以遵循以下步骤:

定义平衡二叉树

空树或左右子树的高度差绝对值不超过1,且左右子树都是平衡二叉树。

递归判断

对于每个节点,计算其左右子树的高度差。

如果高度差绝对值大于1,则该树不是平衡二叉树。

如果左右子树的高度差绝对值不超过1,则递归判断左右子树是否平衡。

计算高度

从叶子节点开始,自底向上逐层累加高度。

高度是从叶节点开始(其高度为1)自底向上逐层累加的,不同叶子节点计算开始计算时,高度不同取最大值。

实现方法

可以使用递归函数,返回一个包含节点高度和是否平衡的结构体。

在递归过程中,如果发现子树不平衡,可以立即返回,避免不必要的计算。

时间复杂度

最优的算法可以在O(n)时间内完成,其中n是树中节点的数量,因为每个节点只被访问一次。

下面是一个简单的C++代码示例,展示了如何实现上述逻辑:

```cpp

class Solution {

public:

bool isBalanced(TreeNode* root) {

int height;

return myBalance(root, height);

}

private:

struct Result {

int height;

bool isBalanced;

Result(int h, bool b) : height(h), isBalanced(b) {}

};

Result myBalance(TreeNode* node, int& height) {

if (node == nullptr) {

height = 0;

return Result(0, true);

}

Result left = myBalance(node->left, height);

if (!left.isBalanced) {

return Result(0, false);

}

Result right = myBalance(node->right, height);

if (!right.isBalanced) {

return Result(0, false);

}

height = 1 + max(left.height, right.height);

return Result(height, abs(left.height - right.height) <= 1);

}

};

```

这个实现方法在判断子树是否平衡的同时计算其高度,从而避免了重复计算,提高了效率。

返回:知识

相关阅读

    最新文章
    猜您喜欢
    热门阅读