LeetCode Balanced Binary Tree

LeetCode解題之Balanced Binary Tree

原題

判斷一棵二叉樹是否是平衡二叉樹，只有當每個節點的左右兩棵子樹的高度差不大於1時，這棵樹才是平衡的。

注意點：

例子:

輸入:

    3
   / \
  9  20
    /  \
   15   7
  /
 14

輸出: False

解題思路

一個節點的高度是它左右兩棵子樹的高度較大值加一，為了使代碼簡練，定義不平衡的子樹的高度為-1，所以在計算每個節點的高度時，要額外判斷左右兩棵子樹是否平衡，如果不平衡（左子樹不平衡 | 右子樹不平衡 | 左右子樹高度差大於1）就直接返回-1。

AC源碼

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self._isBalanced(root) >= 0

    def _isBalanced(self, root):
        if not root:
            return 0
        left, right = self._isBalanced(root.left), self._isBalanced(root.right)
        if left >= 0 and right >= 0 and abs(left - right) <= 1:
            return 1 + max(left, right)
        else:
            return -1


if __name__ == "__main__":
    None