3ms C++ Iterative O(n) time O(1) space solution, Morris Traversal


  • 0
    R
    1. Compare left tree and right tree symmetrically with Morris in-order Traversal Algorithm.
    2. Set return value and stop the symmetrically traversal when finding unmatched part.
    3. Continue Morris Traversal with left tree and right tree separately to make sure we restore tree structures.

    The code is long, but it's easy to understand if you know Morris algorithm. Who can help me to make the code concise?

    class Solution {
    public:
        bool isSymmetric(TreeNode* root) {
            if (root == nullptr)
                return true;
                
            TreeNode* cur = root->left;
            TreeNode* curr = root->right;
            
            if(cur == nullptr || curr == nullptr)
                return (cur == curr);
                
            bool ret = true;
            
            while(cur && curr){
                if(cur->left == nullptr){
                    if (curr->right != nullptr || cur->val != curr->val){
                        ret = false;
                        goto RET;
                    }
                    
                    cur = cur->right;
                    curr = curr->left;
                }
                else {
                    if (curr->right == nullptr){
                        ret = false;
                        goto RET;
                    }
                
                    TreeNode* pre = cur->left;
                    TreeNode* prer = curr->right;
                    while(pre->right != nullptr && pre->right != cur){
                        if (prer->left == nullptr || prer->left == curr){
                            ret = false;
                            goto RET;
                        }
                            
                        pre = pre->right;
                        prer = prer->left;
                    }
                    if(pre->right == nullptr){
                        if(prer->left != nullptr){
                            ret = false;
                            goto RET;
                        }
                        
                        pre->right = cur;
                        cur = cur->left;
                        
                        prer->left = curr;
                        curr = curr->right;
                    }
                    else {
                        if(prer->left != curr || cur->val != curr->val){
                            ret = false;
                            goto RET;
                        }
                            
                        pre->right = nullptr;
                        prer->left = nullptr;
                        
                        cur = cur->right;
                        curr = curr->left;
                    }
                }
            }
            
            ret &= (cur == curr);
    
    RET:
            //cleanup trees;
            while(cur) {
                if(cur->left == nullptr){
                    cur = cur->right;
                }
                else {
                    TreeNode* pre = cur->left;
                    while(pre->right != nullptr && pre->right != cur){
                        pre = pre->right;
                    }
                    
                    if(pre->right == nullptr){
                        pre->right = cur;
                        cur = cur->left;
                    }
                    else {
                        pre->right = nullptr;
                        cur = cur->right;
                    }
                }
            
            }
            
            while(curr) {
                if(curr->right == nullptr){
                    curr = curr->left;
                }
                else {
                    TreeNode* prer = curr->right;
                    while(prer->left != nullptr && prer->left != curr){
                        prer = prer->left;
                    }
                    
                    if(prer->left == nullptr){
                        prer->left = curr;
                        curr = curr->right;
                    }
                    else {
                        prer->left = nullptr;
                        curr = curr->left;
                    }
                }
            }
    
            return ret;
        }
    };

Log in to reply
 

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