110.平衡二叉树

题目描述

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例：

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7
返回 true 。

思路

1.根据平衡二叉树的定义可知，只要有一个结点它的左右子树深度相差超过1便不符合要求。
2.可以额外编写一个函数，用于计算一个结点的左右子树可以达到的深度，若深度差值符合要求，则一直递归下去，否则直接返回false即可。

Java代码实现

    public boolean isBalanced(TreeNode root) {
        if(root != null){
            int leftDepth = treeDepth(root.left);
            int rightDepth = treeDepth(root.right);
            if(Math.abs(leftDepth-rightDepth) <= 1)
                return isBalanced(root.left) && isBalanced(root.right);
            return false;
        }
        return true;
    }

    private int treeDepth(TreeNode root){
        if(root == null)
            return 0;
        return Math.max(treeDepth(root.left),treeDepth(root.right))+1;
    }