Accepted code. Explaination with Algo.


  • 45
    D
    1. Create an empty stack, Push root node to the stack.
    2. Do following while stack is not empty.

    2.1. pop an item from the stack and print it.

    2.2. push the right child of popped item to stack.

    2.3. push the left child of popped item to stack.

    class Solution {
    public:
        vector<int> preorderTraversal(TreeNode *root) {
            stack<TreeNode*> nodeStack;
            vector<int> result;
            //base case
            if(root==NULL)
            return result;
            nodeStack.push(root);
            while(!nodeStack.empty())
            {
                TreeNode* node= nodeStack.top();
                result.push_back(node->val);
                nodeStack.pop();
                if(node->right)
                nodeStack.push(node->right);
                if(node->left)
                nodeStack.push(node->left);
            }
            return result;
            
        }
    };

  • -4
    L

    Same algo, but with list.

    class Solution {
    public:
        vector<int> preorderTraversal(TreeNode *root) {
    		if (!root)
    			return vector<int>();
    
    		vector<int> ans;
    		list<TreeNode*> s;
    		s.push_back(root);
    		while (!s.empty()) {
    			auto head = s.front();
    			s.erase(s.begin());
    			ans.push_back(head->val);
    			if (head->right)
    				s.push_front(head->right);
    			if (head->left)
    				s.push_front(head->left);
    		}
    		return ans;
        }
    };

  • 0
    T

    Nice code! Thanks very much!


  • 0
    A

    i like this idea because it EXACTLY simulates the behavior of stack..


Log in to reply
 

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