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


  • 0
    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;
        }
    };
    

Log in to reply
 

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