Balanced Binary Tree

環(huán)境：python 3.6，scala 2.11.8

題意

判斷一個(gè)二叉樹是否為高度平衡的二叉樹。

一棵高度平衡二叉樹定義為：一個(gè)二叉樹每個(gè)節(jié)點(diǎn)的左右兩個(gè)子樹的高度差的絕對(duì)值不超過 1。

分析

高度平衡的二叉樹，要求左右兩個(gè)子樹的高度差的絕對(duì)值不超過 1。如果能求得樹的深度，才可方便比較左右子樹的高度差。

因此，該題需要理解掌握LC104-二叉樹的最大深度。思路重點(diǎn)是，在遍歷過程中，求每個(gè)左右節(jié)點(diǎn)的最大深度，進(jìn)行比較；

有兩種實(shí)現(xiàn)方法，區(qū)別在于第一種方法是由LC104計(jì)算絕對(duì)深度進(jìn)行比較，而第二種方法則關(guān)注于全局變量和及時(shí)返回的處理上。

代碼

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
  }
}

最后

歡迎交流和補(bǔ)充