要判断一个二叉树是否是平衡二叉树,可以遵循以下步骤:
定义平衡二叉树
空树或左右子树的高度差绝对值不超过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);
}
};
```
这个实现方法在判断子树是否平衡的同时计算其高度,从而避免了重复计算,提高了效率。