Implement a function to check if a binary tree is balanced.
how to solve
A balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one. So I implement a function fetchHeight to get the heights of subtrees. To use a past result of fetchHeight function, I used hash table. If I calculate the height once before. I can get this value in O(1). To calculate the all of the value of fetch Height function, I firstly traverse all nodes in O(n). Next, I can check the all subtree to meet the definition of a balanced tree to answer this question.