O(1) space solution similar to Morris traversal (variant of post-order traversal)


  • 2
    M
    class Solution {
    public:
      TreeNode* invertTree(TreeNode* root) {
        TreeNode aux(0), *p = &aux;
        aux.left = root;
        while (p) {
          TreeNode *q = p->left;
          if (q) {
            while (q->right && q->right != p) q = q->right;
            if (q->right == p) {
              for (TreeNode *r = p->left; ; r = r->left) {
                swap(r->left, r->right);
                if (r == q) break;
              }
              q->left = NULL;
            } else {
              q->right = p;
              p = p->left;
              continue;
            }
          }
          p = p->right;
        }
        return aux.left;
      }
    };
    

    I have elaborated this algorithm in http://maskray.me/blog/2015-06-16-morris-post-order-traversal (Chinese)


  • 0

    Mind-boggling. Well done.


Log in to reply
 

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