https://leetcode.com/problems/balanced-binary-tree/description/
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
package go.jacob.day807; public class Demo4 { public boolean isBalanced(TreeNode root) { if (root == null) return true; return getHeight(root) != -1; } /* * 高度差如果大于1，返回-1 */ private int getHeight(TreeNode root) { if (root == null) return 0; int left = getHeight(root.left); if (left == -1) return -1; int right = getHeight(root.right); if (right == -1) return -1; if (left - right > 1 || right - left > 1) return -1; return 1 + Math.max(left, right); } /* * 错误解法：不能只判断根节点的左右子树是否高度差小于1, 要判断任意节点的左右高度差 */ public boolean isBalanced_1(TreeNode root) { return root == null || Math.abs(height(root.left) - height(root.right)) <= 1 ? true : false; } private int height(TreeNode root) { if (root == null) return 0; return 1 + Math.max(height(root.left), height(root.right)); } }
