题目描述
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过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; }