均衡二叉树
题目形容：给定一个二叉树，判断它是否是高度均衡的二叉树。
本题中，一棵高度均衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例阐明请见LeetCode官网。
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。
解法一：递归
- 首先，增加一个办法height，该办法通过层序遍历的形式失去二叉树的高度。
而后，通过递归法判断二叉树是否是均衡二叉树，递归过程如下：
- 如果以后根节点为空，则间接返回true；
- 否则，计算以后根节点的左右子树的高度，如果以后根节点的左右子树的高度之差不超过1，则递归判断以后根节点的左右子树是否是均衡二叉树；否则，返回false。
import com.kaesar.leetcode.TreeNode;import java.util.LinkedList;import java.util.Queue;public class LeetCode_110 { /** * 递归 * * @param root * @return */ public static boolean isBalanced(TreeNode root) { // 如果以后根节点为null，必定是均衡的，间接返回true if (root == null) { return true; } // 如果以后根节点的左右子树的高度之差不超过1，则递归判断以后根节点的左右子树是否是均衡二叉树 if (height(root.left) - height(root.right) >= -1 && height(root.left) - height(root.right) <= 1) { return isBalanced(root.left) && isBalanced(root.right); } else { return false; } } /** * 层序遍历：通过计算二叉树的层数来失去二叉树的高度 * * @param root 以后根节点 * @return 返回二叉树的高度 */ public static int height(TreeNode root) { int result = 0; if (root == null) { return result; } Queue<TreeNode> nodes = new LinkedList<>(); nodes.add(root); result = 0; while (!nodes.isEmpty()) { result++; int count = nodes.size(); while (count > 0) { TreeNode cur = nodes.poll(); if (cur.left != null) { nodes.add(cur.left); } if (cur.right != null) { nodes.add(cur.right); } count--; } } return result; } public static void main(String[] args) { // 测试用例，冀望返回后果： true TreeNode root = new TreeNode(3); root.left = new TreeNode(9); root.right = new TreeNode(20); root.right.left = new TreeNode(15); root.right.right = new TreeNode(7); System.out.println(isBalanced(root)); }}【每日寄语】 把所有的不快给昨天，把所有的心愿给今天，把所有的致力给明天。