Getting TLE - my code attempts to follow Convert Binary Search Tree (BST) to Sorted Doubly-Linked List


  • 0
    I

    I am basically following convert binary search tree to doubly linked list article but I am getting TLE. Could anyone tell me what I am doing wrong?

    void flatten(TreeNode *root, TreeNode* &prev) {
        if (!root) return;
    
        flatten(root->left, prev);
        if (prev) prev->right = root;
    
        TreeNode* right = root->right;
        root->left = prev;
        prev = root;
        root->right = nullptr;
        flatten(right, prev);
    }
    void flatten(TreeNode *root) {
        TreeNode* prev = nullptr;
        flatten(root, prev);
    }
    

  • 0
    I

    This was my bad. I assumed that the list should return in-order traversal doubly linked list just like the article.
    Upon looking at other people's solution, I learned that I made wrong assumptions.
    I fixed my own mistake and here is my recursive solution. I will look at how other did without recursion... A lot to learn.

    void flatten(TreeNode *root, TreeNode* &prev) {
        if (!root) return;
        
        if (prev) prev->right = root;
        prev = root;
        TreeNode* right = root->right;
        
        flatten(root->left, prev);
        root->left = nullptr;
        flatten(right, prev);
    }
    void flatten(TreeNode *root) {
        TreeNode* prev = nullptr;
        flatten(root, prev);
    }
    

Log in to reply
 

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