9-line C++ recursive solution beat 100% C++ submissions (6ms) with comments


  • 0

    The idea is straightforward as in comments.

        void flatten(TreeNode* r) {
            if (!r) return;
            flatten(r->left);      // flatten left subtree
            auto R = r->right;
            r->right = r->left;   // modify to set flattened left subtree as right subtree
            r->left = NULL;     // remove left subtree
            auto cur = r;
            while (cur->right) cur = cur->right; // find rightmost node after flatten
            flatten(R);                         // flatten right subtree
            cur->right = R;                // append flattened right subtree to rightmost node
        }
    

  • 0

    Just saw Pochman's post about the "beat 100%" statistics and recent OJ upgrade, so stop making fuss about my 100% beat solution :-)

    Actually, as I am originally from Math background, I never quite get why (or how could it ) use the actual running time of a given set of test cases as standard to judge the efficiency of a program. The running time heavily depends on external resource outside of the program. Also, the test cases could be biased as well (theoretically, any finite number of test cases is biased). In Math, once you finished a proof of a problem, it is either right or wrong. There is no such thing (or not I am aware of) to measure how "good" your proof is. I am wondering whether it is possible to have an automatic complexity analyzer to analyze the time and space complexity of a program statically, not at run time as it requires input data which will be biased. I would like to see an automatic way to analyze programs pure theoretically so I can rule out any external source dependency.


Log in to reply
 

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