平衡二叉树

题目描述：给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例说明请见LeetCode官网。

来源：力扣（LeetCode）

链接：

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：递归

首先，添加一个方法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));    }}

【每日寄语】 把所有的不快给昨天，把所有的希望给明天，把所有的努力给今天。