110. Balanced Binary Tree

Question: Balanced Binary Tree

Solution1. bottom up recursive DFS

可以參考 543. Diameter of Binary Tree 的 solution1.

class Solution:

def isBalanced(self, root: Optional[TreeNode]) -> bool:

res = [True]

def get_height(node):

if node == None:

return 0

left_height = get_height(node.left)

right_height = get_height(node.right)

diff = left_height - right_height

if diff > 1 or diff < -1:

res[0] = False

height = 1 + max(left_height, right_height)

return height

get_height(root)

return res[0]

Solution2. bottom up recursive DFS

dfs 時儲存兩個變數 [balance, height]
注意，只要有其中一棵 subtree 是不平衡的，就要回傳 false，所以在存 balance 變數的時候，也要把 left_balance, right_balance 記下來，並考慮進去，跟上一個解法一樣，只是上面解法把 balance 另外存，這邊是每次 call function 的時候都會再當成回傳值回傳。

class Solution:

def isBalanced(self, root: Optional[TreeNode]) -> bool:

def dfs(node):

if node == None:

return True, 0

left_balance, left_height = dfs(node.left)

right_balance, right_height = dfs(node.right)

balance = left_balance and right_balance and abs(left_height - right_height) <= 1

return balance, 1 + max(left_height, right_height)

balance, height = dfs(root)

return balance

Video Solution