刷题记录：判断是不是平衡二叉树

会写最简单的：到根节点时判断左右子树高度

代码如下：

class Solution:
    def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
        if not pRoot:
            return True
        
        if not self.IsBalanced_Solution(pRoot.left) or not self.IsBalanced_Solution(pRoot.right):
            return False
        
        left = self.getHeight(pRoot.left)
        right = self.getHeight(pRoot.right)
        
        return True if abs(left - right) <= 1 else False
        
    
    def getHeight(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        left = self.getHeight(root.left)
        right = self.getHeight(root.right)
        
        return max(left, right) + 1

但是这种做法每到一个根节点就遍历子树，开销很大
看了官解才知道这是自顶向下的做法
除此之外还有自底向上的做法，在回溯的过程中判断是否满足条件
代码如下：

class Solution:
    def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
        return self.depth(pRoot) != -1
        
        
    def depth(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        left = self.depth(root.left)
        if left == -1:
            return -1
        
        right = self.depth(root.right)
        if right == -1:
            return -1
        
        if abs(left - right) > 1:
            return -1
        
        return max(left, right) + 1

除了妙啊我什么都不会