题解 | JZ79 判断是不是平衡二叉树
由于要涉及到子树的高度，而单独递归IsBalanced_Solution()函数是无法涉及到子树高度的，所以需要拎出来子树高度作为一个单独的模块。
得出上面的结论的思考是：在构思IsBalanced_Solution()函数模块的时候，只用考虑当前层和其他层之间的关系，怎么串起来。而串起来的方法就是需要知道子树是否为平衡二叉树，以及当前层满不满足平衡二叉树的要求。而满足平衡二叉树的要求其中一条就是需要左右子树的最大高度差不超过1，因此需要把求子树高度的模块抽出来做一个单独的函数。
class Solution {
public:
bool IsBalanced_Solution(TreeNode* pRoot) {
if (!pRoot) return true;
int left_height = get_height(pRoot->left);
int right_height = get_height(pRoot->right);
if (abs(left_height - right_height) <= 1)
return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
return false;
}
int get_height(TreeNode* root) {
if (!root) return 0;
if (!root->left && !root->right) return 1;
return max(get_height(root->left), get_height(root->right)) + 1;
}
};
}
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pRoot TreeNode类
# @return bool布尔型
#
class Solution:
def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
# write code here
if not pRoot:
return True
left_height = self.get_height(pRoot.left)
right_height = self.get_height(pRoot.right)
if (abs(left_height - right_height) <= 1):
return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
return False
def get_height(self, pRoot: TreeNode) -> int:
if not pRoot:
return 0
if not pRoot.left and not pRoot.right:
return 1
return max(self.get_height(pRoot.left), self.get_height(pRoot.right)) + 1
查看45道真题和解析
