0110._balanced_binary_tree.md

Navigation

Links:

1. https://leetcode.com/problems/balanced-binary-tree/
2. https://leetcode-cn.com/problems/balanced-binary-tree/

Tags

1. 树
2. 深度优先搜索

Solution 1 自顶向下(暴力法))

每次DFS求左右字树的最大高度(刚好这里求高度的方法也是DFS)，然后abs(相减)判断。 就是有两个DFS方法。 本方法产生大量重复的节点访问和计算，最差情况下时间复杂度O(N^2)

class Solution:
    def isBalanced(self, root):
        if not root:
            return True

        left = self.get_height_dfs(root.left)
        right = self.get_height_dfs(root.right)

        if abs(left - right) > 1:
            return False

        return self.isBalanced(root.left) and self.isBalanced(root.right)   # DFS递归判断是否是平衡二叉树

    def get_height_dfs(self, root): # DFS求高度
        if not root:
            return 0
        
        left = self.get_height_dfs(root.left)
        right = self.get_height_dfs(root.right)
        return max(left, right) + 1

Solution 2 从底至顶

从底到顶，这样就可以避免Solution1计算大量重复的节点。 怎么从底往上？DFS是向上返回的。 判断逻辑写在哪里？把“判断是否是平衡树的逻辑”放在求高度的DFS方法中。 当发现不是平衡树时，后面的高度计算都没有意义了，因此一路返回-1。 最差情况是对树做一遍完整DFS，时间复杂度为 O(N)。

class Solution:
    def isBalanced(self, root):
        if not root:
            return True
        
        height = self.get_height_dfs(root)
        return height != -1

        
    def get_height_dfs(self, root):
        if not root:
             return 0

        left = self.get_height_dfs(root.left)
        right = self.get_height_dfs(root.right)

        if left == -1 or right == -1:   # 当前节点的左或右字树不是平衡树的话，就一路向上返回-1。不用在当前节点判断是否是平衡树了。
            return -1          

        if abs(left - right) > 1:
            return -1
            
        return max(left, right) + 1