判断二叉树平衡完整代码
时间: 2024-05-21 19:09:42 浏览: 18
判断二叉树是否平衡的代码可以通过递归实现。一个二叉树是平衡的,当且仅当其左右子树高度差不超过1,且左右子树也分别为平衡二叉树。因此,可以编写以下代码:
```
int height(TreeNode* root) { // 计算以root为根节点的树的高度
if (root == nullptr) {
return 0;
}
int left_height = height(root->left);
int right_height = height(root->right);
return max(left_height, right_height) + 1;
}
bool isBalanced(TreeNode* root) {
if (root == nullptr) { // 空树也是平衡二叉树
return true;
}
int left_height = height(root->left);
int right_height = height(root->right);
if (abs(left_height - right_height) > 1) { // 左右子树高度差超过1,不是平衡二叉树
return false;
}
return isBalanced(root->left) && isBalanced(root->right); // 左右子树也必须是平衡二叉树
}
```
相关问题
python判断平衡二叉树代码
以下是Python判断平衡二叉树的代码:
```
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def treeDepth(root):
if not root:
return 0
return max(treeDepth(root.left), treeDepth(root.right)) + 1
if not root:
return True
leftTreeDepth = treeDepth(root.left)
rightTreeDepth = treeDepth(root.right)
if abs(leftTreeDepth - rightTreeDepth) > 1:
return False
return self.isBalanced(root.left) and self.isBalanced(root.right)
```
该代码使用递归的方式判断二叉树是否平衡。首先定义一个函数`treeDepth`,用于计算二叉树的深度。然后在主函数中,先判断根节点是否为空,如果为空则返回True。接着计算左右子树的深度,如果深度差大于1,则返回False。最后递归判断左右子树是否平衡,如果都平衡则返回True,否则返回False。
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,否则递归判断左右子树是否为平衡二叉树。