题目
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4] 输出：false
示例 3：
输入：root = [] 输出：true
提示：
- 树中的节点数在范围 [0, 5000] 内
- − 1 0 4 -10^4−104 <= Node.val <= 1 0 4 10^4104
解答
方法一：递归
如果左子树或者右子树的高度返回为-1（不是平衡二叉树），那么该树一定不是平衡二叉树，同样返回-1
python解法
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isBalanced(self, root: TreeNode) -> bool: return self.get_depth(root)!=-1 def get_depth(self,root): if not root: return 0 left_depth = self.get_depth(root.left) right_depth = self.get_depth(root.right) if left_depth==-1 or right_depth==-1 or abs(left_depth-right_depth)>1: return -1 else: return 1+max(left_depth,right_depth)
c++解法
class Solution { public: int getDepth(TreeNode* root){ if(!root) return 0; int left_depth=getDepth(root->left); int right_depth=getDepth(root->right); if(left_depth==-1||right_depth==-1||abs(left_depth-right_depth)>1){ return -1; } return 1+max(left_depth,right_depth); } bool isBalanced(TreeNode* root) { return getDepth(root)!=-1; } };
java解法
class Solution { int getDepth(TreeNode root){ if(root==null) return 0; int left=getDepth(root.left); int right=getDepth(root.right); if(left==-1||right==-1||Math.abs(left-right)>1){ return -1; } return Math.max(left,right)+1; } public boolean isBalanced(TreeNode root) { return getDepth(root)!=-1; } }
