admin管理员组文章数量:1529448
一棵树是平衡的,是指该树的每个节点的左右子树的高度差不超过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语言实现的判断树是否平衡的方法,其他编程语言也可根据相同的思路来实现。
本文标签: 如何判断treenode构成的树是否平衡
版权声明:本文标题:如何判断treenode构成的树是否平衡 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/bianchengkaifa/1724218960a970000.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论