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


  • 0
    A

    Basically a variant of Problem 100: Same Tree.
    Honestly, for any problem, recursive solution is always trivial compared to non-recursive solution, so why bother with recursive?

    class Solution {
    public:
        int mt(TreeNode* &t, bool d) {
            int o = 0;
            if (t) {
                if (TreeNode *p = d ? t->right : t->left) {
                    while (d ? p->left && p->left != t : p->right && p->right != t) p = d ? p->left : p->right;
                    if (d ? p->left : p->right) {
                        if (d) p->left = NULL;
                        else p->right = NULL;
                        o = t->val;
                        t = d ? t->left : t->right;
                    } else {
                        if (d) p->left = t;
                        else p->right = t;
                        t = d ? t->right : t->left;
                    }
                } else {
                    o = t->val;
                    t = d ? t->left : t->right;                
                }
            }
            return o;
        }
        bool isSymmetric(TreeNode* root) {
            bool o = true;
            if (!root) return o;
            TreeNode *l = root->left, *r = root->right;
            while (l || r) {
                if (!(l && r)) o = false;
                if (mt(l, false) != mt(r, true)) o = false;
            }
            return o;
        }
    };
    

Log in to reply
 

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