Recursion & non-recursion C++ solution


  • 0
    D
    //recursion
    void invert(TreeNode* root){
    	if (root){
    		swap(root->left, root->right);
    		invert(root->left);
    		invert(root->right);
    	}
    }
    TreeNode* invertTree(TreeNode* root) {
    	invert(root);
    	return root;
    }
    
    //non-recursion
    TreeNode* invertTree(TreeNode* root) {
    	//invert(root);
    	stack<TreeNode*> s;
    	TreeNode *p = root;
    	while (p) {
    		s.push(p);
    		p = p->left;
    	}
    	while (!s.empty()) {
    		TreeNode * t = s.top();
    		s.pop();
    		swap(t->left, t->right);
    		if (t->left) {
    			t = t->left;
    			while (t){
    				s.push(t);
    				t = t->left;
    			}
    		}
    	}
    	return root;
    }

Log in to reply
 

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