题解 | #平衡二叉树#

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
注：我们约定空树是平衡二叉树。
示例1
输入：{1,2,3,4,5,6,7}
返回值：true

题目分析

平衡二叉树是在“二叉树的深度”这题上，对每个结点的左右子树深度分别进行判断是否是超过1，可以采用自顶向下的方法，从根节点开始计算是否平衡，再到子结点；也可以采用自底向上的方法，从叶子结点向根节点判断是否平衡。

解题思路

方法1：自顶向下递归
思路：
1.分别获得根节点的左右子树的高度；
2.若高度差大于1，则直接返回不平衡；
3.否则继续判断根节点的左右子树是否平衡，直到空节点；
图片说明

方法2：自底向上递归
思路：
1.先遍历到叶子结点处的子树；
2.若子树高度差大于1，则直接返回不平衡；
3.否则继续回溯判断上次的节点的左右子树是否平衡，直到根节点；
图片说明

代码实现

方法1：自顶向下递归

    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null) return true;
        // 获取根节点的左右两子树的高度
        int left = path(root.left);
        int right = path(root.right);
        // 如果大于1则不是平衡树
        if(Math.abs(left-right)>1) return false;
        // 否则，继续判断左右子树是否是平衡树
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }

    public int path(TreeNode node){
        // 计算树的最大高度
        if(node == null) return 0;
        int left = path(node.left)+1;
        int right = path(node.right)+1;
        return Math.max(left, right);
    }

时间复杂度： $O(n^2)$ ，需要遍历整个树结点的同时还要计算深度，所以时间复杂度最差情况下为 $O(n^2)$ ；
空间复杂度： $O(n)$ ，递归最大的深度为整个树的结点数，即当树退化成链表时；

方法2：自底向上递归

    public boolean IsBalanced_Solution(TreeNode root) {
        // 设置-1表示非平衡
        return getDepth(root) != -1;
    }

    public 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;
        // 最后判断root的左右子树高度差
        return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
    }

时间复杂度： $O(n)$ ，需要遍历整个树结点；
空间复杂度： $O(n)$ ，递归最大的深度为整个树的结点数，即当树退化成链表时。