招银网络面试真题解析-算法篇-53-判断是不是平衡二叉树

vlambda
2022-03-05

招银网络面试真题解析-算法篇-53-判断是不是平衡二叉树

试题描述：

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

样例解释：

样例二叉树如图，为一颗平衡二叉树

注：我们约定空树是平衡二叉树。

数据范围：n≤100,树上节点的val值满足 0≤n≤1000

要求：空间复杂度O(1)，时间复杂度 O(n)

输入描述：

输入一棵二叉树的根节点

返回值描述：

输出一个布尔类型的值

示例

输入：

{1,2,3,4,5,6,7}

返回值：

true

靓丽分割线：

参考答案：

解题思路：

这道题目其实跟二叉树的深度这道题用到的方法是一样的，具体参考“小米面试真题解析-算法篇-50-二叉树的最大深度”。

根据题目描述，我们只需要判断左右子树的深度之差有没有超过1，若超过了则不是平衡的，反之则为平衡二叉树。

我们只需要在最大深度代码加上判断左右子树的深度之差即可。

代码如下：

 boolean isBalanced = true; // 默认标记为true public boolean IsBalanced_Solution(TreeNode root) { TreeDepth(root); return isBalanced; }

public int TreeDepth(TreeNode root) { if(root == null) return 0; // 递归终止 int l = TreeDepth(root.left); int r = TreeDepth(root.right);

 if(Math.abs(l-r) > 1){ isBalanced = false; // 不是平衡树 }

 return Math.max(l,r)+1; // 求深度 }

但是，上面的代码总是遍历完全部的节点，我们想想，如果一判断到左右子树的深度之差大于1，即这个二叉树就不可能再是平衡树了。

所以，我们还可以对上面代码进行优化。

进行剪枝：当判断到左右子树的深度之差大于1的时候，则返回-1。每次递归结束判断返回值是否-1，若为-1，则立即返回。

所以优化后的代码为：

 boolean isBalanced = true; public boolean IsBalanced_Solution(TreeNode root) { TreeDepth(root); return isBalanced; }

public int TreeDepth(TreeNode root) { if(root == null) return 0; int l = TreeDepth(root.left); if(l == -1) return -1; // 提前返回 int r = TreeDepth(root.right); if(r == -1) return -1; // 提前返回 if(Math.abs(l-r) > 1){ isBalanced = false; // 不是平衡树 return -1; // 加一个标记-1，已经不可能是平衡树了 }

 return Math.max(l,r)+1; }

vlambda博客
学习文章列表