利用二叉树遍历的思想编写一个判断二叉树是否是平衡二叉树的算法
时间: 2023-04-26 11:04:44 浏览: 104
判断二叉树是否是平衡二叉树的算法可以使用二叉树遍历的思想来实现。具体步骤如下:
1. 定义一个函数isBalanced,该函数接收一个二叉树的根节点作为参数。
2. 在isBalanced函数中,首先判断二叉树是否为空,如果为空,则返回true。
3. 然后分别递归遍历二叉树的左子树和右子树,计算它们的高度。
4. 如果左子树和右子树的高度差大于1,则返回false,表示该二叉树不是平衡二叉树。
5. 如果左子树和右子树的高度差小于等于1,则继续递归遍历左子树和右子树,直到遍历完整个二叉树。
6. 如果遍历完整个二叉树后,没有发现左子树和右子树的高度差大于1的情况,则返回true,表示该二叉树是平衡二叉树。
下面是一个示例代码:
```
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
if (Math.abs(leftHeight - rightHeight) > 1) {
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
private int getHeight(TreeNode node) {
if (node == null) {
return ;
}
int leftHeight = getHeight(node.left);
int rightHeight = getHeight(node.right);
return Math.max(leftHeight, rightHeight) + 1;
}
```
其中,getHeight函数用于计算二叉树的高度,isBalanced函数用于判断二叉树是否是平衡二叉树。