Java code running much faster than C++ and C code. Same Logic. WHHHHYYYY???HOWWW?


  • 0
    P

    C++ code. 40ms/36ms : recursive/iterative

    class Solution {
    public:
    TreeNode* ret;

    void findSucc(TreeNode* root, TreeNode* p){
        if(root == NULL)
            return;
        if(root->val < p->val){
            findSucc(root->right, p);
        }
        else if(root->val > p->val){
            ret = root;
            findSucc(root->left, p);
        }
        else
            return;
        return;
    }
    
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode* temp;
        ret = NULL;
        if(root == NULL)
            return NULL;
    
        if(p->right != NULL){
            temp = p->right;
            while(temp->left != NULL){
                temp = temp->left;
            }
            ret = temp;
        }
        else{
            while(root != NULL){
                if(root->val > p->val){
                    ret = root;
                    root = root->left;
                }
                else if(root->val < p->val)
                    root = root->right;
                else
                    break;
            }
        }
        //    findSucc(root, p);
        
        return ret;
    }
    

    };

    C code. 24ms.

    struct TreeNode* inorderSuccessor(struct TreeNode* root, struct TreeNode* p) {
    struct TreeNode *ret = NULL;
    if(root == NULL)
        return NULL;
    
    if(p->right != NULL){
        ret = p->right;
        while(ret->left != NULL){
            ret = ret->left;
        }
    }
    else{
        while(root != NULL){
            if(root->val > p->val){
                ret = root;
                root = root->left;
            }
            else
                root = root->right;
        }
    }
    return ret;
    

    }

    Java solution: 5 ms

    public class Solution {
    private TreeNode cand;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {

        if(p.right!=null){
            TreeNode temp = p.right;
            while(temp.left!=null) temp=temp.left;
            return temp;
        }
        
        else{
            cand = null;
            doJob(root,p);
            return cand;
        }
    }
    
    private void doJob(TreeNode root,TreeNode p){
        if(root==p) return;
        if(p.val<root.val){
            cand = root;
            doJob(root.left,p);
        }
        else doJob(root.right,p);
    }
    

    }


Log in to reply
 

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