The test cases don't cover invalid inputs


  • 0
    H

    I first implemented the algorithm without checking if the tree exists for given inorder and postorder traversals. I wanted to try it before adding the check, and surprisingly It was accepted by the OJ. Now it is obviously that the OJ only have valid inputs as test cases, however I believe when no tree satisfy the inorder and postorder traversal it should return NULL.

    I wrote a c++ program which prints all the results with a postorder of 1,2,3...,n and all permutations of inorder. The following is the output for n = 4:

    hzzyyy@Ubuntu:~/Examples$ a.out 4
    Inorder:        1 2 3 4
    Tree:   4, 3, #, 2, #, 1, #
    Inorder:        1 2 4 3
    Tree:   4, 2, 3, 1, #
    Inorder:        1 3 2 4
    Tree:   4, 3, #, 1, 2
    Inorder:        1 3 4 2
    Tree:   #
    Inorder:        1 4 2 3
    Tree:   4, 1, 3, 2, #
    Inorder:        1 4 3 2
    Tree:   4, 1, 3, #, 2
    Inorder:        2 1 3 4
    Tree:   4, 3, #, 2, #, #, 1
    Inorder:        2 1 4 3
    Tree:   4, 2, 3, #, 1
    Inorder:        2 3 1 4
    Tree:   #
    Inorder:        2 3 4 1
    Tree:   #
    Inorder:        2 4 1 3
    Tree:   #
    Inorder:        2 4 3 1
    Tree:   #
    Inorder:        3 1 2 4
    Tree:   4, 3, #, #, 2, 1, #
    Inorder:        3 1 4 2
    Tree:   #
    Inorder:        3 2 1 4
    Tree:   4, 3, #, #, 2, #, 1
    Inorder:        3 2 4 1
    Tree:   #
    Inorder:        3 4 1 2
    Tree:   #
    Inorder:        3 4 2 1
    Tree:   #
    Inorder:        4 1 2 3
    Tree:   4, #, 3, 2, #, 1, #
    Inorder:        4 1 3 2
    Tree:   4, #, 3, 1, 2
    Inorder:        4 2 1 3
    Tree:   4, #, 3, 2, #, #, 1
    Inorder:        4 2 3 1
    Tree:   #
    Inorder:        4 3 1 2
    Tree:   4, #, 3, #, 2, 1, #
    Inorder:        4 3 2 1
    Tree:   4, #, 3, #, 2, #, 1
    Postorder:      1 2 3 4

Log in to reply
 

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