LeetCode 110.平衡二叉树 python/scala

Balanced Binary Tree

环境：python 3.6，scala 2.11.8

题意

判断一个二叉树是否为高度平衡的二叉树。

一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

分析

高度平衡的二叉树，要求左右两个子树的高度差的绝对值不超过 1。如果能求得树的深度，才可方便比较左右子树的高度差。

因此，该题需要理解掌握LC104-二叉树的最大深度。思路重点是，在遍历过程中，求每个左右节点的最大深度，进行比较；

有两种实现方法，区别在于第一种方法是由LC104计算绝对深度进行比较，而第二种方法则关注于全局变量和及时返回的处理上。

代码

python

def isBalanced(root):
    """
    :type root: TreeNode
    :rtype: bool
    """
    if not root: return True
    left, right = maxDepthV2(root.left), maxDepthV2(root.right)    # 这里引用 lc104 的 maxDepthV2
    return abs(left - right) <= 1 and isBalanced(root.left) and isBalanced(root.right)


def isBalancedV2(root):
    if not root: return True
    rs = [1]

    def dfs(node):
        if not node or not rs[-1]: return 0
        left, right = dfs(node.left), dfs(node.right)
        if abs(left - right) > 1:
            rs[-1] = 0
            return 0
        return 1 + max(left, right)
    dfs(root)
    return bool(rs[-1])

scala

object LC110 {
  def isBalanced(root: TreeNode): Boolean = {
    if (root == null) return true
    val (left, right) = (maxDepthV2(root.left), maxDepthV2(root.right)) // # 这里引用 lc104 的 maxDepthV2
    math.abs(left - right) <= 1 & isBalanced(root.left) & isBalanced(root.right)
  }

  def isBalancedV2(root: TreeNode): Boolean = {
    if (root == null) return true

    var rs = true

    def dfs(node: TreeNode): Int = {
      if (node == null | !rs) return 0
      val (left, right) = (dfs(node.left), dfs(node.right))
      if (math.abs(left - right) > 1) {
        rs = false
        0
      } else {
        1 + math.max(left, right)
      }
    }

    dfs(root)

    rs
  }

  // isBalancedV2 另一种写法
  def isBalancedV3(root: TreeNode): Boolean = {
    var balance = true

    def go(node: TreeNode): Int = node match {
      case null => 0
      case _ if !balance => 0
      case _ => {
        val (left, right) = (go(node.left), go(node.right))
        if (math.abs(left - right) <= 1) 1 + math.max(left, right)
        else {balance = false; 0}
      }
    }
    go(root)
    balance
  }
}

最后

欢迎交流和补充