C++ solution 3ms using Morris Traversal 3ms


  • 0
    L
    vector<int> preorderTraversal(TreeNode* root) {
            TreeNode *cur = root, *pre;
            vector<int> result;
            while(cur != NULL)
            {
                pre = cur->left;
                if(pre == NULL)
                {
                    result.push_back(cur->val);
                    cur = cur->right;
                }
                else
                {
                    while(pre->right != NULL && pre->right != cur)
                        pre = pre->right;
                    if(pre->right == NULL)
                    {
                        result.push_back(cur->val);
                        pre->right = cur;
                        cur = cur->left;
                    }
                    else
                    {
                        pre->right = NULL;
                        cur = cur->right;
                    }
                }
            }
            return result;
        }

  • 0
    J

    vector<int> preorderTraversal(TreeNode* root) {

     vector<int> tree(0);
    if (root==NULL)
    {
    	return tree ;
    }
    
    stack<TreeNode *> s;
    TreeNode *p = root;
    s.push(p);
    while(!s.empty())
    {
    	p = s.top();
    	s.pop();
    	tree.push_back(p->val);
    	if (p->right!=NULL)
    	{
    		s.push(p->right);
    	}
    	if(p->left)
    		s.push(p->left);
    }
    return tree;
        
    }
    

    };


Log in to reply
 

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