给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
解答
/** * 辅助方法,用于计算当前树节点的高度。 * @param node 树节点 * @return 高度 */ public int depth(TreeNode node) { if (node == null) { return 0; } int left = depth(node.left); int right = depth(node.right); return Math.max(left, right) + 1; } /** * 按照题目要求,检查当前节点是否平衡。 * @param root 树节点 * @return true表示平衡 */ public boolean isBalanced(TreeNode root) { if (root == null) { return true; } if (!isBalanced(root.left) || !isBalanced(root.right)) { return false; } int left = depth(root.left); int right = depth(root.right); if (Math.abs(left - right) > 1) { return false; } return true; }
要点
注意点:基于树的特点,使用递归方法来求解。
- 题目中对平衡二叉树的定义,要求计算给定节点的高度。
- 检查给定节点左、右子树的高度之差,是否在1以内。
- 兼顾效率,减少无意义的计算,先递归,再求解。
若非注明,均为原创,欢迎转载,转载请注明来源:LeetCode第110题 – 平衡二叉树