144. Binary Tree Preorder Traversal

Difficulty: Medium

Frequency: N/A

Given a binary tree, return the preorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traverse(root, result);
        return result;
    }
    void traverse(TreeNode* node, vector<int>& result) {
        if (!node) return;
        result.push_back(node->val);
        traverse(node->left, result);
        traverse(node->right, result);
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
Advertisements

103. Binary Tree Zigzag Level Order Traversal

Difficulty: Medium

Frequency: N/A

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> results;
        if (!root) return results;
        deque<TreeNode*> deq;
        deq.push_front(root);
        bool front = true;
        while (!deq.empty()) {
            int s_size = deq.size();
            vector<int> result;
            while (s_size) {
                if (front) {
                    TreeNode *cur = deq.front();
                    deq.pop_front();
                    result.push_back(cur->val);
                    if (cur->left) deq.push_back(cur->left);
                    if (cur->right) deq.push_back(cur->right);
                } else {
                    TreeNode *cur = deq.back();
                    deq.pop_back();
                    result.push_back(cur->val);
                    if (cur->right) deq.push_front(cur->right);
                    if (cur->left) deq.push_front(cur->left);
                }
                s_size--;
            }
            front = !front;
            results.push_back(result);
        }
        return results;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

224. Basic Calculator

Difficulty: Medium

Frequency: N/A

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int calculate(string s) {
        int result = 0, num = 0, sign = 1;
        stack<int> tmp;
        for (char c : s) {
            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+') {
                result = result + sign * num;
                num = 0;
                sign = 1;
            } else if (c == '-') {
                result = result + sign * num;
                num = 0;
                sign = -1;
            } else if (c == '(') {
                tmp.push(result);
                tmp.push(sign);
                result = 0;
                sign = 1;
            } else if (c == ')') {
                result = result + sign * num;
                result = result * tmp.top();
                tmp.pop();
                result = result + tmp.top();
                tmp.pop();
                num = 0;
            }
        }
        result += num * sign;
        return result;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

255. (Locked)Verify Preorder Sequence in Binary Search Tree

Difficulty: Medium

Frequency: N/A

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Follow up:
Could you do it using only constant space complexity?


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {  
public:  
    bool verifyPreorder(vector<int>& preorder) {  
        int low = INT_MIN;
        stack<int> path;
        for (int p : preorder) {
            if (p < low) return false;
            while (!path.empty() && p > path.top()) low = path.pop();
            path.push(p);
        }
        return true;
    }
}

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

232. Implement Queue using Stacks

Difficulty: Easy

Frequency: N/A

Implement the following operations of a queue using stacks.

  • push(x) — Push element x to the back of queue.
  • pop() — Removes the element from in front of queue.
  • peek() — Get the front element.
  • empty() — Return whether the queue is empty.

Notes:

  • You must use only standard operations of a stack — which means only push to top, peek/pop from top, size, and is empty operations are valid.
  • Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
  • You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Queue {
public:
    // Push element x to the back of queue.
    void push(int x) {
        stack<int> tmp;
        while (!s.empty()) {
            tmp.push(s.top());
            s.pop();
        }
        s.push(x);
        while (!tmp.empty()) {
            s.push(tmp.top());
            tmp.pop();
        }
    }

    // Removes the element from in front of queue.
    void pop(void) {
        s.pop();
    }

    // Get the front element.
    int peek(void) {
        return s.top();
    }

    // Return whether the queue is empty.
    bool empty(void) {
        return s.empty();
    }
private:
    stack<int> s;
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

155. Min Stack

Difficulty: Easy

Frequency: N/A

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) — Push element x onto stack.
  • pop() — Removes the element on top of the stack.
  • top() — Get the top element.
  • getMin() — Retrieve the minimum element in the stack.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class MinStack {
public:
    void push(int x) {
        if (trackMin.empty() || x <= getMin()) trackMin.push(x);
        s.push(x);
    }

    void pop() {
        if (trackMin.top() == s.top()) trackMin.pop();
        s.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return trackMin.top();
    }
private:
    stack<int> s, trackMin;
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

225. Implement Stack using Queues

Difficulty: Easy

Frequency: N/A

Implement the following operations of a stack using queues.

  • push(x) — Push element x onto stack.
  • pop() — Removes the element on top of the stack.
  • top() — Get the top element.
  • empty() — Return whether the stack is empty.

Notes:

  • You must use only standard operations of a queue — which means only push to back, peek/pop from front, size, and is empty operations are valid.
  • Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
  • You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Stack {
public:
    // Push element x onto stack.
    void push(int x) {
        queue<int> tmp;
        while (!q.empty()) {
            tmp.push(q.front());
            q.pop();
        }
        q.push(x);
        while(!tmp.empty()) {
            q.push(tmp.front());
            tmp.pop();
        }
    }

    // Removes the element on top of the stack.
    void pop() {
        q.pop();
    }

    // Get the top element.
    int top() {
        return q.front();
    }

    // Return whether the stack is empty.
    bool empty() {
        return q.empty();
    }
private:
    queue<int> q;
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn: