N-ary Tree Preorder Traversal

Given the root of an n-ary tree, return the preorder traversal of its nodes' values.

/*
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}
    Node(int _val) { val = _val; }
    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> traverse(Node* node) {
        vector<int> result;
        if (!node) return result;
        
        function<void(Node*)> dfs = [&](Node* current) {
            result.push_back(current->val);
            for (Node* child : current->children) {
                dfs(child);
            }
        };
        
        dfs(node);
        return result;
    }
};

N-ary Tree Postorder Traversal

Given the root of an n-ary tree, return the postorder traversal of its nodes' values.

/*
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}
    Node(int _val) { val = _val; }
    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> traverse(Node* node) {
        vector<int> result;
        if (!node) return result;
        
        function<void(Node*)> dfs = [&](Node* current) {
            for (Node* child : current->children) {
                dfs(child);
            }
            result.push_back(current->val);
        };
        
        dfs(node);
        return result;
    }
};

Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[', and ']', detemrine if the input string is valid.

class Solution {
public:
    bool isValid(string input) {
        stack<char> buffer;
        unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };

        for (char ch : input) {
            if (pairs.count(ch)) {
                if (buffer.empty() || buffer.top() != pairs[ch]) {
                    return false;
                }
                buffer.pop();
            } else {
                buffer.push(ch);
            }
        }
        return buffer.empty();
    }
};

Binary Tree Inorder Travresal

Given the root of a binary tree, return the inorder traversal of its nodes' values.

/**
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> output;
        function<void(TreeNode*)> visit = [&](TreeNode* node) {
            if (!node) return;
            visit(node->left);
            output.push_back(node->val);
            visit(node->right);
        };
        visit(root);
        return output;
    }
};

Distinct Subsequences

Given two strings s and t, return the number of distinct subsequences of s which equals t. The answer should be returned modulo $10^9 + 7$.

class Solution {
public:
    int numDistinct(string src, string target) {
        int srcLen = src.length(), tgtLen = target.length();
        const int MOD = 1000000007;
        
        // dp[i][j] means number of ways to form target[0..j-1] using src[0..i-1]
        vector<vector<long long>> dp(srcLen + 1, vector<long long>(tgtLen + 1, 0));
        
        // Base case: empty target can be formed by any prefix of src in 1 way
        for (int i = 0; i <= srcLen; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= srcLen; i++) {
            for (int j = 1; j <= tgtLen; j++) {
                // If we don't use src[i-1]
                dp[i][j] = dp[i - 1][j];
                
                // If src[i-1] matches target[j-1], we can use it
                if (src[i - 1] == target[j - 1]) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD;
                }
            }
        }
        return dp[srcLen][tgtLen];
    }
};