Leetcode 110. Balanced Binary Tree (python+cpp)

题目

解析：

自上而下，到每个节点队规判断左右两边是否平衡，不平衡立刻返回false，平衡则递归判断最有两边子树是否平衡。判断平衡方法为直接求出两边的深度
python代码如下：

class Solution:def isBalanced(self, root: TreeNode) -> bool:def get_depth(root):return 1+max(get_depth(root.left),get_depth(root.right)) if root else 0if not root:return Trueif abs(get_depth(root.left)-get_depth(root.right))>1:return Falseelse:return self.isBalanced(root.left) and self.isBalanced(root.right)

C++代码如下：

class Solution {
    
public:bool isBalanced(TreeNode* root) {
    if (!root) return true;if (abs(get_depth(root->left)-get_depth(root->right))>1){
    return false;}else return isBalanced(root->left) && isBalanced(root->right);}int get_depth(TreeNode* root){
    return root ? 1+max(get_depth(root->left),get_depth(root->right)) : 0;}
};

这种解法其实有很多重复计算，每个深度为d的节点的高度会被判断d次，所以相较于上面top down的方式，bottom up更合理。但是这边就不展示了，因为并不重要

二刷

我也不知道为啥一刷的时候根本不care所需的optimization，每个节点被访问height次其实很伤，所以可以用一个variable来在算深度的时候就判断是否平衡。注意这种nonlocal或者是global的variable直接用class的属性变量代替

# 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 __init__(self):self.is_balance = Truedef isBalanced(self, root: Optional[TreeNode]) -> bool:def get_depth(node):if not node:return 0left_h = get_depth(node.left)right_h = get_depth(node.right)if abs(left_h - right_h) > 1:self.is_balance = Falsereturn max(left_h,right_h) + 1get_depth(root)return self.is_balance