Balanced Binary Tree: Tree Height

First Thoughts: binary tree balanced if longest route (from root to leaf) and shortest route (from root to leaf) difference is less than 2. but there were edge cases where this was not the case. in fact, balanced tree depends on the height of the tree -> make height function. and tree balanced if left and right subtrees balanced, and height difference is less than two.

My Solution:

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root==null) return true;
        ArrayList<Integer> branchCounts = new ArrayList<>();
        if (root.left==null || root.right==null) branchCounts.add(0);
        counter(root, 0, branchCounts);
        int minCount = Collections.min(branchCounts);
        int maxCount = Collections.max(branchCounts);
        return !(maxCount-minCount>1);
    }
        
    public void counter(TreeNode root, int count, ArrayList<Integer> branchCounts) {
        if (root==null) {
            
            return;
        }
        if (root.left==null && root.right==null) {
            branchCounts.add(count);
            return;
        }
        counter(root.left, count+1, branchCounts);
        counter(root.right, count+1, branchCounts);
        if (root.left!=null) {
            
            counter(root.left, count+1, branchCounts);
        }
        if (root.right!=null) {
            
            counter(root.right, count+1, branchCounts);
        }
        
    }
}

Improved Solution:

public boolean isBalanced(TreeNode root) {
	if (root==null) return true;
    boolean current = Math.abs(height(root.left)-height(root.right)<2);
    return current && isBalanced(root.left) && isBalanced(root.right);
}
public int height(TreeNode root) {
	if (root==null) return -1;
    return 1 + Math.max(height(root.left), height(root.right));
}

Catch Point

1. Tree balance is tightly connected to difference in tree height (height of tree refers to the 층의 위치) 그 층수가 2이상 차이가 나면 balanced가 아닌것. 그럼 그 subtree를 포함하는 tree도 그냥 모두 balanced가 아니게 된다.

2. 따라서 한 tree가 balanced려면 하나라도 imbalanced subtree가 있으면 안된다.

3. Use of helper methods to get height of tree, recursion and && operator to check all balance status of left and right subtrees.