字节面试题——判断一棵树是否为平衡二叉树

4. 判断一棵树 是否为 平衡二叉树（时间复杂度：O(N^2)）

原题链接

*****不用管递归的逻辑，只需根据最上边根节点写出代码即可

    // 获取二叉树的高度 时间复杂度：O(N)
    int getHeight(TreeNode root) {
    
        if(root == null) return 0;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return (leftHeight > rightHeight ?
                leftHeight+1 : rightHeight+1);
    }
    //时间复杂度：O(N^2)
    public boolean isBalanced(TreeNode root) {
    
        if(root == null) return true;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.abs(leftHeight-rightHeight) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }

优化，当出现不平衡情况，便不再进行递归，而是依次return -1

优化时候的思考角度，便是从下往上思考

    //这个题 是字节考过的原题 O(n)
    public int maxDepth(TreeNode root) {
    
        if(root == null) return 0;
        int leftTree = maxDepth(root.left);
        int rightTree = maxDepth(root.right);

        if(leftTree >= 0 && rightTree >= 0 && Math.abs(leftTree - rightTree) <= 1) {
    
            return Math.max(leftTree,rightTree) + 1;
        }else {
    
            return -1;
        }
    }

    public boolean isBalanced2(TreeNode root) {
    
        if(root == null) return true;
        return maxDepth(root) >= 0;
    }

***** 解决思想

原方法是：求根节点的 左右子树的高度后比较，
然后 再去判断左右子树的子树的分别高度差，这样就会递归两次 时间复杂度为（O N²）

修改方法：是只遍历一次，在求树的高度的时候，判断是否为平衡二叉树，如果不是，便停止计算 便是 O（N）