Test case wrong


  • 3
    L

    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?


  • 0
    L

    It's balanced. the depth of a tree is the same as the max depth of the tree.


  • 1
    Q

    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.


  • 0
    D

    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


  • 0
    D

    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:

    1. Left subtree of T is balanced
    2. Right subtree of T is balanced
    3. The difference between heights of left subtree and right subtree is not more than 1.

  • 0
    S

    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.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.