Does anyone know why second DFS(12 ms) is slower than first DFS(8ms) solution?


  • 2
    S

    8ms:

    class Solution {
    private:
        TreeNode* biggest(TreeNode* root){
            if(!root->right) return root;
            return biggest(root->right);
        }
    public:
        void flatten(TreeNode* root) {
            if(!root) return;
            if(root->left){
                TreeNode* tmp = biggest(root->left);
                tmp->right = root->right;
                root->right = root->left;
                root->left = NULL;
            }
            flatten(root->right);
        }
    };
    

    12ms:

    class Solution {
    public:
        void flatten(TreeNode* root) {
            if(!root) return;
            if(root->left){
                TreeNode* tmp = root->left;
                while(tmp->right) {
                    tmp = tmp->right;
                }
                tmp->right = root->right;
                root->right = root->left;
                root->left = NULL;
            }
            flatten(root->right);
        }
    };

  • 0
    T

    because there may be many nodes before tmp reaches the right end


Log in to reply
 

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