Diagonal Traversal

• Time : $O(n)$
• Space : $O(n)$

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
void dfs(TreeNode* node, unordered_map<int, vector<int>>& mp, vector<int>& seq, int y, int x) {
    if(!node) return;
    int hash = y - x;
    if(!mp.count(hash)) seq.push_back(hash);
    mp[hash].push_back(node->val);
    dfs(node->left, mp, seq, y + 1, x - 1);
    dfs(node->right, mp, seq, y + 1, x + 1);
}
vector<int> Solution::solve(TreeNode* A) {
    unordered_map<int, vector<int>> mp;
    vector<int> seq;
    dfs(A,mp,seq,0,0);
    
    vector<int> res;
    for(auto s : seq) {
        for(auto v : mp[s]) {
            res.push_back(v);
        }
    }
    return res;
}