LeetCode_27_BalancedBinaryTree

1. question: 平衡二叉树（简单）

给定一个二叉树，判断它是否是高度平衡的二叉树。

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/balanced-binary-tree

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

提示：

树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104

2. answers

注意，这里将高度和深度混为一谈，均为高度的意思。

这道题最直观的方法就是求解左右子树的高度，然后判断高度差。注意，如果高度差相差小于等于1并不意味着一定是平衡二叉树，因为可能左右子树根本就不是平衡二叉树。所以还需要判断左右子树是否是平衡二叉树。

代码如下所示：

public class Solution_0025 {

    public static boolean isBalanced(TreeNode root) {

        if(root == null) {
            return true;
        }

        int left_depth = getDepth(root.left);
        int right_depth = getDepth(root.right);

        // 如果高度差大于1，说明肯定不是二叉树，不用再进行后续判断。
        if(Math.abs(left_depth - right_depth) > 1) {
            return false;
        }

        // 如果高度差小于等于1，则需要判断左右子树是否是平衡二叉树。
        boolean leftResult = isBalanced(root.left);
        boolean rightResult = isBalanced(root.right);

        return leftResult && rightResult;
    }

    // 求解一棵树的高度。
    public static int getDepth(TreeNode root) {

        if(root == null) {
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int length, depth = 0;

        while(!queue.isEmpty()) {

            length = queue.size();
            depth ++;
            while(length > 0) {
                root = queue.poll();

                if(root.left != null) {
                    queue.offer(root.left);
                }

                if(root.right != null) {
                    queue.offer(root.right);
                }

                length --;

            }
        }

        return depth;
    }

    public static void main(String[] args) {
        System.out.println();

        TreeNode tn1 = new TreeNode(15);
        TreeNode tn2 = new TreeNode(7);
        TreeNode tn3 = new TreeNode(20, tn1, tn2);
        TreeNode tn4 = new TreeNode(9);
        TreeNode tn5 = new TreeNode(3, tn3, tn4);

        System.out.println(isBalanced(tn5));
    }
}

仔细分析一下，其实上述层序遍历求解高度的操作重复了很多次（每次递归都要层序遍历一次，而且每次递归都重复遍历了）。这其实是没必要的。怎么优化呢？

在求解深度的时候，其实就要判断该节点是否为平衡二叉树。

怎么判断呢？左右孩子节点的高度差不大于1.（如果是，那么该节点的高度就是孩子节点高度的最大值加1；如果不是，就直接返回-1，无需后续的判断了）

因此，这就形成了递归。

代码如下所示：

public class Solution_0025_02 {

    public static boolean isBalanced(TreeNode root) {

        return getDepth(root) != -1;
    }

    public static int getDepth(TreeNode root) {

        if(root == null) {
            return 0;
        }

        // 获取左节点的高度
        int left = getDepth(root.left);

        // 如果左孩子节点返回值为-1，表示不是平衡二叉树，所以直接返回即可，无序后续判断。
        if(left == -1) {
            return -1;
        }

        int right = getDepth(root.right);

        if(right == -1) {
            return -1;
        }

        // 如果高度差大于1，说明不是当前节点不是平衡二叉树，返回-1
        if(Math.abs(left - right) > 1) {
            return -1;
        }

        // 说明当前节点是平衡二叉树，返回其高度，注意左右子节点的最大值 + 1（当前节点）
        return Math.max(left, right) + 1;
    }

    public static void main(String[] args) {

        TreeNode tn1 = new TreeNode(15);
        TreeNode tn2 = new TreeNode(7);
        TreeNode tn3 = new TreeNode(20, tn1, tn2);
        TreeNode tn4 = new TreeNode(9);
        TreeNode tn5 = new TreeNode(3, tn3, tn4);

        System.out.println(isBalanced(tn5));
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。