Level Order Traversal of Binary Tree

Problem: Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

Solution: 
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

vector<vector<int> > levelOrder(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > ans;
        if (!root) return ans;
       
        vector<TreeNode *> nodeVec;
        nodeVec.push_back(root);
       
        int it = 0;
        int rowIt;
        int rowLimit;
        while (it < nodeVec.size()) {
            vector<int> row;
            rowLimit = nodeVec.size();
            for (rowIt = it; rowIt < rowLimit; rowIt++) {
                row.push_back(nodeVec[rowIt]->val);
                if (nodeVec[rowIt]->left)
                    nodeVec.push_back(nodeVec[rowIt]->left);
                if (nodeVec[rowIt]->right)
                    nodeVec.push_back(nodeVec[rowIt]->right);
            }
            ans.push_back(row);
            it = rowLimit;
        }
        return ans;
    }
};

For getting the traversal in reverse order, you can reverse the final solution of above.

vector <vector<int> > sol;
for (it = ans.size() - 1; it >= 0; it--) {
            sol.push_back(ans[it]);
}
return sol;

=================== Second Time =======================


class Solution {
public:
    vector<vector<int> > levelOrder(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > solution;
        queue<TreeNode *> queue;
        TreeNode *popedNode = NULL;

        if (root == NULL)
            return solution;

        queue.push(root);
        int row_length = 1;
 
        while (!queue.empty()) {
            vector<int> row;
            for (int i = 0; i < row_length; i++){
                popedNode = queue.front();
                queue.pop();
                row.push_back(popedNode->val);
                if (popedNode->left != NULL)
                    queue.push(popedNode->left);
                if (popedNode->right != NULL)
                    queue.push(popedNode->right);
            }
            solution.push_back(row);
            row_length = queue.size();
        }
        return solution;
    }
};

====== Third attempt ========
/**
 * 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>> levelOrder(TreeNode* root) {
        vector<TreeNode *> cur, child;
        vector<vector<int> > sol;
        vector<int> row;
       
        if (root == NULL) {
            return sol;
        }
       
        cur.push_back(root);
        sol.push_back(vector<int>(1, root -> val));
        int i = 0;
        while (i < cur.size()) {
            if (cur[i] -> left != NULL ) {
                child.push_back(cur[i] -> left);
                row.push_back(cur[i] -> left -> val);
            }
            if (cur[i] -> right != NULL ) {
                child.push_back(cur[i] -> right);
                row.push_back(cur[i] -> right -> val);
            }
            i++;
            if (i == cur.size()) {
                if (row.size() != 0) {
                    sol.push_back(row);
                    row.clear();
                }
                cur = child;
                child.clear();
                i = 0;
            }
        }
        return sol;
    }
};

Easy one of LeetCode

Binary Inorder Traversal

class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> solTree;
        if (root == NULL) {
            //solTree.push_back(NULL);
            return solTree;
        }
       
        if (root->left) {
            vector<int> leftTree;
            leftTree = inorderTraversal(root->left);
            solTree = leftTree;
        }
        solTree.push_back(root->val);
        if (root->right) {
            vector<int> rightTree;
            rightTree = inorderTraversal(root->right);
            solTree.insert(solTree.end(), rightTree.begin(), rightTree.end());
        }
        return solTree;
    }
};

Best time to buy and sell stock

problem:
Say you have an array for which the i^th element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Solution:


class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (prices.size() < 2) {
            return 0;
        }
        int minSoFar = prices[0];
        int maxSoFar = prices[0];
        int bestBuy = 0;
        int maxBestBuy = 0;
        int it;
        for(it = 1; it < prices.size(); it++) {
            if (prices[it] >= maxSoFar) {
                maxSoFar = prices[it];
                bestBuy = maxSoFar - minSoFar;
                maxBestBuy = max(bestBuy, maxBestBuy);
            }
            else if (prices[it] <= minSoFar) {
                minSoFar = prices[it];
                maxSoFar = prices[it];
            }
        }
        return maxBestBuy;
    }
};

Balanced Binary Tree

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    int height (TreeNode *root) {
        if (root == NULL)
            return 0;
        else
            return max(height(root -> left), height(root -> right)) + 1;
    }
   
    bool isBalanced(TreeNode *root) {
        if (root == NULL)
            return true;
        else if ((abs(height(root -> left) - height(root -> right)) < 2) &&
                isBalanced(root -> left) && isBalanced(root -> right))
            return true;
        return false;
    }
};