一棵樹是平衡的,是指該樹的每個節點的左右子樹的高度差不超過1。要判斷一個由TreeNode構成的樹是否平衡,可以通過遞歸的方式來判斷每個節點的左右子樹的高度差是否小于等于1。
具體步驟如下:
示例代碼如下:
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語言實現的判斷樹是否平衡的方法,其他編程語言也可根據相同的思路來實現。