平衡二叉树

Leetcode Link: 剑指 Offer 55 - II. 平衡二叉树 - 力扣（LeetCode）

题目

解法一：DFS

思路： 类似二叉树的最大深度，当左右子树的深度差>1，则res=False，最后返回False

题解：

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        res = True
        def dfs(node):
            nonlocal res
            if not node:
                return 0
            
            left = dfs(node.left)
            right = dfs(node.right)
 
            if abs(left-right) > 1:
                res = False
            
            return max(left, right)+1
        
        dfs(root)
        return res

本题不是纯递归，整了一个闭包的形式，不是很优雅，但是似乎也没有很优雅的方法

解法二：从下到上DFS+剪枝

思路： 解法一中没有剪枝，当我们遇到一个不合格的时候，就可以完成剪枝，此外，结果只是一个状态，我们可以用数字-1来表示当前的结果已经不是平衡二叉树了

题解：

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def dfs(node):
            if not node:
                return 0
            
            left = dfs(node.left)
            if left == -1: return -1
            right = dfs(node.right)
            if right == -1: return -1
 
            return max(left, right)+1 if abs(left-right)<=1 else -1
 
        return dfs(root) != -1

解法三

思路：

题解：

启发和联系