How can use this sequence to create a binary search tree?


  • 0
    W

    I am try to solve this problem, but wrong with this case

    Input: {68,41,#,-85,#,-73,-49,-98,#,#,#,-124}
    Output: {68,-73,#,-85,#,41,-49,-98,#,#,#,-124}
    Expected: {68,41,#,-73,#,-85,-49,-98,#,#,#,-124}

    I think all sequence is the pre order traverse sequence, but i don't think expected can create a normal binary search tree


  • 1
    M

    That's because the inputs and outputs are written using a modified level-order traversal, not preorder. The # means end of line of descent, not just "This is a null element." This is actually shown in several tree problems under the "confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ." link.

    Input:

                68
               /
             41
            /
          -85
          /  \
        -73 -49
        /
      -98
      /
    -124
    

    The expected answer has -85 and -73 swapped and so looks like this:

                68
               /
             41
            /
          -73
          /  \
        -85 -49
        /
      -98
      /
    -124
    

    Yours, on the other hand, swapped 41 and -73 and so looks like this:

                68
               /
             -73
            /
          -85
          /  \
        41  -49
        /
      -98
      /
    -124
    

  • 0
    W

    thank you very much


Log in to reply
 

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