Input:
[1,2,2,3,3,3,3,4,4,4,4,4,4,null,null,5,5]
Output:
false
Expected:
true
This test case is a tree like the following:
1
2 2
3 3 3 3
4 4 4 4 4 4
5 5
It is not balanced, right?
Ok, got it. It is more clear from more explicit definition. Heights of left and right subtress are in did not different by more then 1 inspite min depth and max depth are different by 2:
An empty tree is height-balanced. A non-empty binary tree T is balanced if:
1st level: left depth=4, right depth=3
2nd level: left.left depth=3, right.right depth=2. right.left depth=2, right.right=1
... and so on.
Each parent is balanced and both children of each parent are balanced, then the tree is balanced.
I guess your codes is level-order travel, so you get this result.