Why Iterative solution is slower than recursive solution?


  • 0
    B

    I am using common inorder-traversal both in iteration and recursion.

    but, iteration version got 56ms, and recursion version got 48ms.

    did anyone know the reason?

    Here goes the code:

    Iteration:

    class Solution {
    public:
        void recoverTree(TreeNode* root) {
            if(!root) return;
            TreeNode * cur = root, * pre = nullptr, *first = nullptr, * second = nullptr;
            stack<TreeNode*> stk;
            while(cur||!stk.empty()){
                while(cur){
                    stk.push(cur);
                    cur = cur->left;
                }
                cur = stk.top();
                stk.pop();
                if(pre && cur->val < pre->val){
                    if(!first) {
                        first = pre;
                        second = cur;   
                    }
                    else{
                        second = cur;
                        swap(first, second);
                        return;
                    }
                }
                pre = cur;
                cur = cur->right;
            }
            swap(first, second);
        }
        void swap(TreeNode* first, TreeNode* second){
            if(!first || !second) return;
            int tmp = first->val;
            first->val = second->val;
            second->val = tmp;
        }
    };
    

    Recursion:

    class Solution {
    private:
    public:
        void recoverTree(TreeNode* root) {
            TreeNode * pre = nullptr, * first = nullptr, * second = nullptr;
            traversal(root, pre, first, second);
            swap(first, second);
        }
        
        void traversal(TreeNode * root, TreeNode * & pre, TreeNode * &first, TreeNode * &second){
            if(!root) return;
            traversal(root->left, pre, first, second);
            if(pre && root->val < pre->val){
                if(!first){
                    first = pre;
                    second = root;
                }else second = root;
            }
            pre = root;
            traversal(root->right, pre, first, second);
        }
        
        void swap(TreeNode* first, TreeNode* second){
            if(!first || !second) return;
            int tmp = first->val;
            first->val = second->val;
            second->val = tmp;
        }
    };

  • 0
    T

    The time difference is within the error of margin, the leetcode timer is not the most accurate.


Log in to reply
 

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