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

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

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