110. Balanced Binary Tree #
题目 #
给定一棵二叉树，判断其是否为高度平衡的二叉树。
高度平衡二叉树定义为：每个节点的左右两个子树的高度差的绝对值不超过1。
思路 #
- 编写代码的过程中会发现，需要类型分别为
boolean和int的两个返回值，对应以 root 为根节点的树是否高度平衡和以 root 为根节点的树的高度 - 鉴于树高为非负整数，故负整数可用于表示
以 root 为根节点的树非高度平衡 - 树的高度通过子树的高度计算得出。且负树高具有传递性。
代码 #
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
/** 以 -1 表示 root 非高度平衡二叉树 */
public int depth(TreeNode root) {
if (root == null) return 0;
int leftDepth = depth(root.left);
if (leftDepth == -1) return -1;
int rightDepth = depth(root.right);
if (rightDepth == -1) return -1;
if (Math.abs(leftDepth - rightDepth) > 1) return -1;
return 1 + Math.max(leftDepth, rightDepth);
}
public boolean isBalanced(TreeNode root) {
return depth(root) != -1;
}
}