LeetCode: Balanced Binary Tree

// https://code.dennyzhang.com/balanced-binary-tree
// Basic Ideas: recursive
//
// Complexity: Time O(n), Space O(h)
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func dfs(root *TreeNode) (int, bool) {
    if root == nil { return 0, true  }
    h1, ok1 := dfs(root.Left)
    if ! ok1 {
        return 0, false
    }
    h2, ok2 := dfs(root.Right)
    if ! ok2 {
        return 0, false
    }
    if h1 < h2 {
        h1, h2 = h2, h1
    }
    if h1-h2>1 {
        return 0, false
    }
    return h1+1, true
}

func isBalanced(root *TreeNode) bool {
    _, ok := dfs(root)
    return ok
}

## https://code.dennyzhang.com/balanced-binary-tree
# 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
        """
        (status, _level) = self._isBalanced(root)
        return status

    def _isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: (bool, level)
        """
        if root is None:
            return (True, 0)
        if root.left is None and root.right is None:
            return (True, 1)

        (l_status, l_level) = self._isBalanced(root.left)
        if l_status is False:
            return (False, -1)
        (r_status, r_level) = self._isBalanced(root.right)
        if r_status is False:
            return (False, -1)

        if (abs(l_level - r_level)>1):
            return (False, -1)
        return (True, max(l_level, r_level) + 1)