[Leetcode] Balanced Binary Tree

Problem

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.

Definition

• The depth of a node is the number of edges from the node to the tree's root node.

A root node will have a depth of 0.

• The height of a node is the number of edges on the longest path from the node to a leaf.

A leaf node will have a height of 0.


For each node in the tree
   If !(leftSubTree is balanced && rightSubTree is balanced && abs(leftDepth - rightDepth) <=1)
       return false
   EndIf
EndFor

This algorithm has a O(n*Log(n)) running time, since for each node we need to call two height function, which has a running time O(Log(n)). The algorithm below has a better running time O(n).
If a tree is not balanced, height return -1.
This is a special technique for this problem, since the depth of a tree must be non-negative. Generally, we can create a result class, which has a boolean isBalanced field and a int depth field.

     

Code