Why Input:{1,3} output can not be {1,3} ?


  • 0
    J

    My code is as below. I got error:
    Submission Result: Wrong Answer
    Input: {1,3}
    Output: {1,3}
    Expected: {3,1}

    Why Output:{1,3} is wrong? Thanks.

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    /**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode *sortedListToBST(ListNode *head) {
            if(!head) {
                return nullptr;
            } else if (!head->next) {
                return new TreeNode(head->val);
            }
            ListNode *s1 = head, *s2 = head, *prev=head;
            while(s2->next != nullptr && s2->next->next != nullptr) {
                s1=s1->next;
                s2=s2->next->next;
                prev = s1;
            }
            s2 = s1->next;
            prev->next = nullptr;
            if(s1==head) {
                //two nodes case: {1,3}. head should be nullptr, s2 is the second node
                head = nullptr;
            }
            return helper(head, s2, s1->val);
        }
        TreeNode *helper(ListNode *head1, ListNode *head2, int val) {
            TreeNode *root = new TreeNode(val);
            if(head1) {
                ListNode *s1 = head1, *s2 = head1, *prev=head1;
                while(s2->next != nullptr && s2->next->next != nullptr) {
                    s1=s1->next;
                    s2=s2->next->next;
                    prev = s1;
                }
                s2 = s1->next;
                prev->next = nullptr;
                if(s1==head1) {
                    head1 = nullptr;
                }
                root->left =  helper(head1, s2, s1->val);
            } else {
                root->left =  nullptr;
            }
            if(head2) {
                ListNode *s1 = head2, *s2 = head2, *prev=head2;
                while(s2->next != nullptr && s2->next->next != nullptr) {
                    s1=s1->next;
                    s2=s2->next->next;
                    prev = s1;
                }
                s2 = s1->next;
                prev->next = nullptr;
                if(s1 == head2) {
                    head2 = nullptr;
                }
                root->left =  helper(head2, s2, s1->val);
            } else {
                root->left =  nullptr;
            } 
            return root;
        }
            
    };

  • 1
    S

    (1, 3) is wrong because 3 is the left child of 1. This is apparently not a BST. You can pass with (1, #, 3) though.


  • 0
    J

    Thanks a lot for the help. I found the bug: in the last 3th line, it should be "root->right= helper(head2, s2, s1->val);" rather than "root->left = helper(head2, s2, s1->val);"
    With this change, now I got error: Output Limit Exceeded.
    What does this error mean? Thanks.


  • 0
    S

    For this problem, it means the output tree contains more nodes than it should have had. You may want to double check thw logic.


Log in to reply
 

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