Leetcode: Balanced Binary Tree

Given a binary tree, determine if it is height-balanced



Similar Problems:


Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## Blog link: 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)
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.