题解 | #平衡二叉树#

算法步骤

1. 判断当前节点是否满足平衡的要求（左右子树高度差不超过1）

2. 满足1并不能保证其左右子树是平衡二叉树，因此需要递归判断 左子树是否平衡，右子树是否平衡

3. 若当前节点及其左右子树都满足平衡的要求，则整个树是平衡二叉树，否则不是平衡二叉树

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return dfs(root);
    }

    //深度优先搜索 判断node树是否我平衡二叉树
    private boolean dfs(TreeNode node)
    {
        if(node==null)
        {
            return true;
        }
        //判断node是否平衡
        boolean IsBalanced=false;
        if(Math.abs(height(node.left)-height(node.right))<=1)
            IsBalanced = true;
        else
            IsBalanced = false;

        //递归判断左子树是否平衡
         boolean l= dfs(node.left);
        //递归判断右子树是否平衡
         boolean r= dfs(node.right);
         return IsBalanced && l && r;
    }

    //计算树的高度
    private int height(TreeNode node)
    {
        if(node==null)
            return 0;
        if(node.left==null && node.right==null)
            return 1;
        int l = height(node.left);
        int r = height(node.right);
        return Math.max(l,r)+1;
    }
}