平衡二叉樹(shù)

題目

給定一個(gè)二叉樹(shù)，判斷它是否是高度平衡的二叉樹(shù)。

本題中，一棵高度平衡二叉樹(shù)定義為：

一個(gè)二叉樹(shù)每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1。

示例 1:

給定二叉樹(shù) [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回 true 。

示例 2:

給定二叉樹(shù) [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

返回 false 。

解答

• 思路：

  • 直接遞歸計(jì)算每個(gè)節(jié)點(diǎn)左右子樹(shù)的高度;
  • 根據(jù)AVL樹(shù)的特性，如果任意一個(gè)節(jié)點(diǎn)的左右子樹(shù)的高度差大于一，則該樹(shù)不是AVL樹(shù)，標(biāo)記器高度為-1;
  • 如果某個(gè)子樹(shù)的高度計(jì)算為-1,則表示該子樹(shù)不是AVL樹(shù)，-1會(huì)一直傳遞到頂層。

• 代碼：

  def isBalanced(self, root):
      """
      :type root: TreeNode
      :rtype bool
  
      (knowledge)
  
      思路：
      1. 直接遞歸計(jì)算每個(gè)節(jié)點(diǎn)左右子樹(shù)的高度;
      2. 根據(jù)AVL樹(shù)的特性，如果任意一個(gè)節(jié)點(diǎn)的左右子樹(shù)的高度差大于一，則該樹(shù)不是AVL樹(shù)，標(biāo)記器高度為-1;
      3. 如果某個(gè)子樹(shù)的高度計(jì)算為-1,則表示該子樹(shù)不是AVL樹(shù)，-1會(huì)一直傳遞到頂層。
      """
      def preOrderTraversal(root):
          if not root:
              return 0
          leftNum = preOrderTraversal(root.left)
          rightNum = preOrderTraversal(root.right)
          if leftNum == -1 or rightNum == -1 or abs(leftNum - rightNum) > 1:
              return -1
          return 1 + max(leftNum, rightNum)
      return preOrderTraversal(root) != -1
  

測(cè)試驗(yàn)證

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

    def __repr__(self):
        if self:
            return "{}->{}->{}".format(self.val, repr(self.left), repr(self.right))


class Solution:
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype bool

        (knowledge)

        思路：
        1. 直接遞歸計(jì)算每個(gè)節(jié)點(diǎn)左右子樹(shù)的高度;
        2. 根據(jù)AVL樹(shù)的特性，如果任意一個(gè)節(jié)點(diǎn)的左右子樹(shù)的高度差大于一，則該樹(shù)不是AVL樹(shù)，標(biāo)記器高度為-1;
        3. 如果某個(gè)子樹(shù)的高度計(jì)算為-1,則表示該子樹(shù)不是AVL樹(shù)，-1會(huì)一直傳遞到頂層。
        """
        def preOrderTraversal(root):
            if not root:
                return 0
            leftNum = preOrderTraversal(root.left)
            rightNum = preOrderTraversal(root.right)
            if leftNum == -1 or rightNum == -1 or abs(leftNum - rightNum) > 1:
                return -1
            return 1 + max(leftNum, rightNum)
        return preOrderTraversal(root) != -1