平衡二叉树判断迭代法
时间: 2023-11-06 07:03:14 浏览: 45
平衡二叉树是一种特殊的二叉树,它的左子树和右子树的高度差不超过1。判断一个二叉树是否是平衡二叉树可以使用迭代法。具体方法是遍历每个节点,计算其左子树和右子树的高度差,如果有任何一个节点不满足平衡条件,则整个二叉树都不是平衡二叉树。
代码示例:
```
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1) {
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
private int getHeight(TreeNode node) {
if (node == null) {
return 0;
}
return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}
}
```
相关问题
平衡二叉树判断左旋右旋
平衡二叉树的左旋和右旋操作是为了保持排序二叉搜索树的平衡性质。左旋和右旋操作可以通过旋转节点和它的子节点来调整树的结构,以确保左子树和右子树的高度差不超过1。左旋是将节点的右子节点提升为根节点,同时将原来的根节点作为新根节点的左子节点。右旋是将节点的左子节点提升为根节点,同时将原来的根节点作为新根节点的右子节点。这样可以保持二叉搜索树的有序性质,并且使得树的高度尽可能平衡。
c语言判断平衡二叉树
平衡二叉树是一种特殊的二叉搜索树,它的左右子树的高度差不超过1。以下是判断平衡二叉树的C语言代码实现:
```c
// 定义二叉树结点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 计算树的高度
int height(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftHeight = height(root->left);
int rightHeight = height(root->right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
// 判断平衡二叉树
bool isBalanced(TreeNode* root) {
if (root == NULL) {
return true;
}
int leftHeight = height(root->left);
int rightHeight = height(root->right);
if (abs(leftHeight - rightHeight) > 1) {
return false;
}
return isBalanced(root->left) && isBalanced(root->right);
}
```
以上代码中,`height`函数用于计算树的高度,`isBalanced`函数用于判断平衡二叉树。在`isBalanced`函数中,首先判断当前节点的左右子树高度差是否超过1,如果超过1则返回false,否则递归判断左右子树是否为平衡二叉树。