Test case wrong

  • 3


    This test case is a tree like the following:

          2       2
        3   3   3   3
       4 4 4 4 4 4 
      5 5

    It is not balanced, right?

  • 0

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

  • 1

    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

    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

    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

    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.