leetcode7-110. Balanced Binary Tree

1. problem

1. balance tree, left - right height not more than 1
2. subtree fit this rule

2. init

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:

3. thought

1. get each node’s left/right height. do math.
2. if unbalance happened in farthest node, O(n^2)

4. trouble

1. n^2
2. -1 is really useful

5.final solution

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        # 1. no root check
        # 2. check left/right hight diff > 1, add in return False
        # 3. no False, check sub node
        if not root: return True
        if abs(self.depth(root.left) - self.depth(root.right)) > 1: return False 
        return self.isBalanced(root.left) and self.isBalanced(root.right)
    def depth(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        return 1 + max(self.depth(root.left) , self.depth(root.right) )

Nice, but worst case go trought n node, n depth compare in each node, find Flase in farthest node.

but if we check any falut balance from bottom, we only go trough n node.
and make use of -1 in number.

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        # 1. depth starting at most left node, build value from bottom  
        # 2. check left/right hight diff > 1, add in return -1 (False in number XD)
        # 3. no -1, any value is ok 
        return self.depth(root) != -1
    def depth(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        leftDepth = self.depth(root.left)
        if leftDepth == -1: return -1
        rightDepth = self.depth(root.right)
        if rightDepth == -1: return -1
        if abs(leftDepth - rightDepth) > 1: return -1
        return 1 + max(self.depth(root.left) , self.depth(root.right) )