判断是否是平衡二叉树
平衡二叉树是指左右子树的高度差不超过1。
需要先求得二叉树的高度。
二叉树的左右子树可能高度不同，应该以子树高的那个作为树的高度。
public int depth(TreeNode root) {if (root == null) {return 0;}int left = depth(root.left);int right = depth(root.right);return Math.max(left, right) + 1;}
平衡二叉树的判断：左右子树的高度差
public boolean isBalance(TreeNode root) {if (root == null) {return true;}int left = depth(root.left);int right = depth(root.right);if (Math.abs(left - right) > 1) {return false;}return isBalance(root.left) && isBalance(root.right);}
上面的实现可能会对下面的节点访问多次。
需要后序遍历。
public boolean isBalance(TreeNode root) {return depth(root) >= 0;}public int depth(TreeNode root) {if (root == null) {return 0;}int left = depth(root.left);int right = depth(root.right);if (left == -1 || right == -1 || Math.abs(left - right) > 1) {return -1;}return Math.max(left, right) + 1;}