如何判断treenode构成的树是否平衡
导读:一棵树是平衡的,是指该树的每个节点的左右子树的高度差不超过1。要判断一个由TreeNode构成的树是否平衡,可以通过递归的方式来判断每个节点的左右子树的高度差是否小于等于1。 具体步骤如下: 编写一个函数 getHeight(TreeNo...
一棵树是平衡的,是指该树的每个节点的左右子树的高度差不超过1。要判断一个由TreeNode构成的树是否平衡,可以通过递归的方式来判断每个节点的左右子树的高度差是否小于等于1。
具体步骤如下:
- 编写一个函数 getHeight(TreeNode node),用于计算以node为根节点的树的高度。
- 编写一个函数 isBalanced(TreeNode node),用于判断以node为根节点的树是否平衡。在该函数中,递归地判断node的左子树和右子树是否平衡,并且判断左子树和右子树的高度差是否小于等于1。
- 在主函数中,调用isBalanced函数,传入根节点,即可判断整棵树是否平衡。
示例代码如下:
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
public int getHeight(TreeNode node) {
if (node == null) {
return 0;
}
return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}
public boolean isBalanced(TreeNode node) {
if (node == null) {
return true;
}
int leftHeight = getHeight(node.left);
int rightHeight = getHeight(node.right);
if (Math.abs(leftHeight - rightHeight) >
1) {
return false;
}
return isBalanced(node.left) &
&
isBalanced(node.right);
}
public static void main(String[] args) {
Solution solution = new Solution();
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
boolean isBalanced = solution.isBalanced(root);
System.out.println("Is the tree balanced? " + isBalanced);
}
}
以上是用Java语言实现的判断树是否平衡的方法,其他编程语言也可根据相同的思路来实现。
声明:本文内容由网友自发贡献,本站不承担相应法律责任。对本内容有异议或投诉,请联系2913721942#qq.com核实处理,我们将尽快回复您,谢谢合作!
若转载请注明出处: 如何判断treenode构成的树是否平衡
本文地址: https://pptw.com/jishu/686236.html