Recursive Solution - Balanced Binary Tree

The idea is to compare heights of sub trees of each node… the calculation is to find the depth of the node, which uses the recursive call. However, in order avoid duplicates calculation, a hash map is defined as global for lookup.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    Map<TreeNode, Integer> heights = new HashMap<TreeNode, Integer>();
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        return isBalanced(root.left) && isBalanced(root.right) && (Math.abs(depth(root.left) - depth(root.right)) < 2);
    }
   
    private int depth(TreeNode node){
        if(node == null){
            return 0;
        }
        if(heights.containsKey(node)){
            return heights.get(node);
        }
        int leftDepth = depth(node.left);
        int rightDepth = depth(node.right);
        int nodeDepth = (leftDepth > rightDepth)? leftDepth + 1 : rightDepth + 1;
        heights.put(node, nodeDepth);
        return nodeDepth;
    }
}