A simple Python recursive solution - 172ms


  • 10
    G
    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        # @param {TreeNode} root
        # @return {boolean}
        def isBalanced(self, root):
            if not root:
                return True
    
            return abs(self.getHeight(root.left) - self.getHeight(root.right)) < 2 and self.isBalanced(root.left) and self.isBalanced(root.right)
    
        def getHeight(self, root):
            if not root:
                return 0
    
            return 1 + max(self.getHeight(root.left), self.getHeight(root.right))

  • 0
    S

    Thanks for sharing your answer! Helpful! I have a question about function 'def isBalanced()'. The balance factor of any node of an AVL tree is in the integer range [-1,+1]. So this function should return abs(...) <= 1. Yes?


  • 0
    G
    This post is deleted!

  • 0
    G

    < 2 is the same as <= 1, correct? ;)


  • 0
    S

    Yes, you are right! And with function 'def getHeight()', the height of each node we get is larger than the actual height of them by ONE, yes? For example, leaves should have height 0, but we get height 1 by this function.


  • 0
    P

    Great answer. A question is why you only consider self.isBalanced(root.right) in the final return, where is self.isBalanced(root.left)? Thanks


  • 0
    G

    the root.left is also in the final return statement :)

    return abs(self.getHeight(root.left) - self.getHeight(root.right)) < 2 and self.isBalanced(root.left) and self.isBalanced(root.right)


  • 0
    P

    my bad! :) I missed that. Thanks!


  • 1
    L

    Is this solution O(n^2)?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.