Why do we need "Morris Traversal", since it's pretty slow.


  • -1
    J

    Waste too much time on finding leftmost child, it is not so useful.
    The standard code shows blow. I guess no one could make it faster, which currently only beats 0.2%.

    class Solution {
      public:
        vector<int> inorderTraversal(TreeNode *root) {
            vector<int> res;
    
            TreeNode *curr = root;
            while (curr) {
                if (!curr->left) {
                    res.push_back(curr->val);
                    curr = curr->right;
                }
    
                else {
                    TreeNode *leftmost_child =
                        find_leftmost_child(curr->left, curr);
                    if (leftmost_child->right == NULL) {
                        leftmost_child->right = curr;
                        curr = curr->left;
                    }
    
                    else {
                        leftmost_child->right = NULL;
                        res.push_back(curr->val);
                        curr = curr->right;
                    }
                }
            }
    
            return res;
        }
    
        TreeNode *find_leftmost_child(TreeNode *node, TreeNode *parent) {
            while (node->right && node->right != parent) {
                node = node->right;
            }
            return node;
        }
    };
    

  • 0

    @jimzuolin said in Why do we need "Morris Traversal", since it's pretty slow.:

    currently only beats 0.2%.

    But what was the percentage of submissions it got beaten by?

    I just submitted it as is. It only beat 0.51%, yeah. But it got beaten by only 40.27%. Because it's among the 59.22% that all took 3 ms. So it looks average. Not super bad, like you tried to make it look like.

    Edit: Submitted it two more times, once it got 3 ms again and next it got 0 ms. So that was among the fastest 40.27%, beating the remaining 59.73%.

    You appear to be totally clueless and wrongly bad-mouthing a totally fine algorithm.


Log in to reply
 

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