题解 | #平衡二叉树#（附带图解）

思路:

从题中给出的有效信息：

• 左右两个子树的高度差的绝对值不超过1
• 左右两个子树都是一棵平衡二叉树

故此 首先想到的方法是使用递归的方式判断子节点的状态

方法一：dfs

具体做法：
如果一个节点的左右子节点都是平衡的，并且左右子节点的深度差不超过 1，则可以确定这个节点就是一颗平衡二叉树。
具体过程如下图所示：

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) return true;
        //判断左子树和右子树是否符合规则，且深度不能超过2
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right) && Math.abs(deep(root.left) - deep(root.right)) < 2;
    }
    //判断二叉树深度
    public int deep(TreeNode root) {
        if (root == null) return 0;
        return Math.max(deep(root.left), deep(root.right)) + 1;
    }
}

复杂度分析：

• 时间复杂度：O(n^2), n 是二叉树中的节点个数
• 空间复杂度：O(n),主要是递归方***占用本地方法栈，而递归层数不会超过n次

方法二：回溯

具体做法：
对于父节点，需要确定两个子节点深度之差小于一。对于作为子节点的立场，需要向自己的上一级节点传递的自己深度

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(deep(root)==-1) return false;
        return true;   
    }
     public int deep(TreeNode node){
        if(node==null) return 0;
        int left=deep(node.left);
        if(left == -1 ) return -1;
        int right=deep(node.right);
        if(right == -1 ) return -1;

        //两个子节点深度之差小于一
        if((left-right)>1 || (right-left)>1){
            return -1;
        }
        //父节点需要向自己的父节点报告自己的深度
        return (left>right?left:right)+1;
    }
}

复杂度分析：

• 时间复杂度：O(n) 其中 n 是所有节点个数
• 空间复杂度：O(n) 主要是递归方***占用本地方法栈，而递归层数不会超过n次