Recursive And Non-recursive C++


  • 1
    J
    // recursive
    TreeNode* invertTree(TreeNode* root) {
            if(!root) return NULL;
            TreeNode* lc = root->left;
            root->left = invertTree(root->right);
            root->right =  invertTree(lc);
            return root;
        }
        
        TreeNode* invertTree(TreeNode* root) {
            if(!root) return NULL;
            invertTree(root->left);
            invertTree(root->right);
            swap(root->left, root->right);
            return root;
        }
    // non-recursive
    TreeNode* invertTree(TreeNode* root) {
            if(!root) return NULL;
            stack<TreeNode*> S;
            S.push(root);
            TreeNode* temp = root;
            while(!S.empty()){
                if((S.top()->left != temp)&&(S.top()->right != temp)){
                    while(temp = S.top()){
                        if(temp->right) S.push(temp->right);
                        if(temp->left) S.push(temp->left);
                        if(temp == S.top()) break;
                    }
                }
                temp = S.top();
                S.pop();
                swap(temp->left, temp->right);
            }
            return root;
        }
    
    TreeNode* invertTree(TreeNode* root) {
            if(!root) return NULL;
            stack<TreeNode*> S;
            S.push(root);
            TreeNode* temp = root;
            while(!S.empty()){
                temp = S.top();
                S.pop();
                swap(temp->left, temp->right);
                if(temp->right) S.push(temp->right);
                if(temp->left) S.push(temp->left);
            }
            return root;
        }

  • 0
    L

    It seems that you used stack to simulate the recursion.


Log in to reply
 

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