[数据结构与算法]力扣第110题“平衡二叉树”的解题思路

参考代码

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        int left=maxDepthleft(root.left);
        int right=maxDepthright(root.right);
        int a=left-right;
        if(a>1||a<-1){
            return false;
        }
        return isBalanced(root.left)&&isBalanced(root.right);
    }
    public int maxDepthleft(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=maxDepthleft(root.left);
        int right=maxDepthleft(root.right);
        return Math.max(left,right)+1;
    }
    public int maxDepthright(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=maxDepthright(root.left);
        int right=maxDepthright(root.right);
        return Math.max(left,right)+1;
    }
}

用到第104求二叉树最大深度的方法，先求出根节点的左右子树的深度，再递归，求出每一个节点左孩子右孩子的深度，保证每一次的绝对值小于等于一即是平衡二叉树。