C++ Non-recursive O(1) space, based on Morris Traversal


  • 2
    A

    Not a fan of recursive. Stack space is also space, otherwise we wouldn't have the "STACKOVERFLOW".

    class Solution {
    public:
        int m(TreeNode *&h) {
            int v = 0;
            if (h) {
                v = h->val;
                if (TreeNode *p = h->left) {
                    while (p->right && p->right != h) p = p->right;
                    if (p->right) {
                        h = h->right;
                        p->right = NULL;
                    } else {
                        p->right = h;
                        h = h->left;
                    }
                } else {
                    h = h->right;
                }
            }
            return v;
        }
        bool isSameTree(TreeNode* p, TreeNode* q) {
            bool o = true;
            while (p || q) {
                if (!(p&&q)) o = false;
                if (m(p) != m(q)) o = false;
            }
            return o;
        }
    };
    

  • 0
    R

    nice solution!
    I spend a long time to understand how this algorithm ensures two tree are structurally identical.


  • 0

    It is really a good solution!
    However I am wondering if there exist such a situation that p and q has different structure, but when go through them using Morris Traversal, the value of two nodes(one is from p, the other is from q) are just the same?
    It seems that in the situation I supposed above, your solution will also output true.

    Thanks!


Log in to reply
 

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