1468: 檢查二叉樹的平衡性

面試題 04.04. 檢查平衡性

實作一個函數，檢查二叉樹是否平衡。在這個問題中，平衡樹的定義如下：任意一個節點，其兩棵子樹的高度差不超過 1。

方法一：

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

class Solution:
    def layer_num(self, root): # 統計以root為根結點的樹的高度
        if root is None :
            return 0
        else:
            return max(self.layer_num(root.left), self.layer_num(root.right)) + 1

    def isBalanced(self, root: TreeNode) -> bool:
    	# 如果根結點是空或者它的左右結點為空，則平衡
        if root is None or (root.left is None and root.right is None):
            return True
        # 如果左右子樹平衡而且左右子樹的層數（高度）差不大于1則平衡
        if (self.isBalanced(root.left) and self.isBalanced(root.right) 
        and abs(self.layer_num(root.left) - self.layer_num(root.right)) <= 1):
            return True
        # 否則不平衡
        else:
            return False
           

這種方法效果不好，因為遞歸本身的效率就不高，這裡不止用了一種遞歸，isBalanced和layer_num都用到了遞歸，是以導緻效率低下。

方法二：

class Solution:
	def isBalanced(self, root):
	        return self.getHeight(root, 0) != -1
	    
	def getHeight(self, head, depth):
	    if head == None:
	        return depth
	    
	    left = self.getHeight(head.left, depth)
	    if left == -1:
	        return -1
	    
	    right = self.getHeight(head.right, depth)
	    if right == -1:
	        return -1
	    
	    if abs(left - right) > 1:
	        return -1
	    
	    return max(left, right) + 1