Solution on visiting Tree in different order (TODO)


  • 0
    F

    Step 1 build a shadow Range Search Tree, every level's nodes are sorted.
    since the [3, 4, 6, 5] could be split in [3,4,6] [5] 2 sub arrays
    and [9, 1, 2, 5, 8, 3] could be split in [9] [1,2,5,8] [3] 3 subarrays
    then build 2 trees
    tree 1
    root
    3,4,6
    5

    tree 2
    root
    9
    1,2,5,8
    3

    so if visit those trees by levels, it maintains the array order.
    and if visit those trees by in-order
    eg: 6,5,4,3 or 9 ,8 ,5, 3,2,1 it maintained the sorted order

    now just combine those 2 array together
    [3, 4, 6, 5, 9, 1, 2, 5, 8, 3]

    root

    3, 4, 6
    |
    -------
    | |
    5, 9
    |
    | |
    | |


    | | |
    [1,2,5],8
    |
    3
    so Binary Range Search Tree if visit by level. maintains original array order
    and the Binary Search 's post-order visit maintained the sorted,
    and visit K step means find K elements

    [9,8,6,5,3]


Log in to reply
 

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