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?
It's balanced. The depth of the left node of the node 1 is 4, and the depth of the right node of the node is 3. 4 and 3 are not differed by more than 1 so it's balanced.
leftmost node of node 1 appears to be on level 5 while rightmost node on level 3. I'm also puzzled with this test case
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:
- Left subtree of T is balanced
- Right subtree of T is balanced
- The difference between heights of left subtree and right subtree is not more than 1.
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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.