牛客网_剑指offer题集——平衡二叉树（java实现）

题目链接：

https://www.nowcoder.com/practice/e02fdb54d7524710a7d664d082bb7811?tpId=13&tqId=11193&tPage=2&rp=2&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking

思路：

两层递归嵌套：第一层递归循环判断树中每一个节点的左右子树深度的差是否都为-1,0,1中的一种，第二层递归则获得左右子树的深度供第一层递归使用

source code：

package niuke;

public class 平衡二叉树 {
    /**
     * 通过遍历来判断左右两边树深度差值是否小于一
     * @param root
     * @return
     */
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null) return true;
        if(Math.abs(compare_the_deep(root.left)-compare_the_deep(root.right))>1){
            return false;
        }
        return IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
    }


    /**
     * 还是求最大深度
     * @param root
     * @return
     */
    public int compare_the_deep(TreeNode root){
        if(root==null) return 0;
        return Math.max(compare_the_deep(root.left),
                compare_the_deep(root.right))+1;

    }
}

代码已ac

希望对大家有所帮助

以上