Is the balanced BST constructed from a sorted array unique?


  • 0
    X

    For an array [1, 2, 3, 4], which of the following is considered its valid balanced BST counterpart,
    {2, 1, 3, #, #, #, 4} or {3, 2, 4, 1}? They seem both valid to me. But does the oj only AC the former (or the latter)? If yes, the problem description shall make this clear.


  • 0
    E

    I think oj can accept both.
    In the recursive solution, if u replace mid = (left+right)/2 with mid = (left+right)/2, instead of always tending to the left bound, middle pointer would tend to the right bound.
    So in this case, 3 would be chosen as the root rather than 2. I got both pass, which means oj have considered both cases.


Log in to reply
 

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