今日题目
T110 平衡二叉树(简单，二叉树，递归)
题目描述
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3/ \9 20/ \15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1/ \2 2/ \3 3/ \4 4
返回 false 。
标签
二叉树，递归
解析
首先另写一个getDepth()函数求树的深度。对根结点，判断树左右子树高度差的绝对值是否小于1，如果满足则对左右子结点递归该过程。
C++解法
class Solution
{
public:int getDepth(TreeNode *root){if (root == nullptr){return 0;}else{int left = getDepth(root->left);int right = getDepth(root->right);return max(left, right) + 1;}}bool isBalanced(TreeNode *root){if (root == nullptr){return true;}int left = getDepth(root->left);int right = getDepth(root->right);int ans = left - right;if (ans < -1 || ans > 1){return false;}return isBalanced(root->left) && isBalanced(root->right);}
};
python解法
class Solution:def getDepth(self, root: TreeNode) -> int:if not root:return 0return max(self.getDepth(root.left), self.getDepth(root.right)) + 1def isBalanced(self, root: TreeNode) -> bool:if not root:return Trueleft, right = self.getDepth(root.left), self.getDepth(root.right)return abs(left - right) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)