1. 题目列表

• 查询后的偶数和（简单模拟）
• 从叶结点开始的最小字符串（二叉树深搜 + 字符串比较）
• 区间列表的交集（区间贪心，two pointer）
• 二叉树的垂序遍历（二叉树的遍历）

2. 查询后的偶数和

直接模拟。

代码：

class Solution {
public:
    vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int>>& queries) {
        vector<int> res;
        int sum = 0;
        for (int i = 0; i < A.size(); i++)
            if (A[i] % 2 == 0) sum += A[i];
        for (int i = 0; i < queries.size(); i++){
            if (A[queries[i][1]] % 2 == 0)
                sum -= A[queries[i][1]];
            A[queries[i][1]] += queries[i][0];
            if (A[queries[i][1]] % 2 == 0)
                sum += A[queries[i][1]];
            res.push_back(sum);
        }
        return res;
    }
};

3. 从叶结点开始的最小字符串

二叉树DFS搜索+路径记录。

代码：

/**
 * 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<TreeNode*> path, temp;
    string smallestFromLeaf(TreeNode* root) {
        temp.push_back(root);
        DFS(root);
        string res = "";
        for (int i = path.size() - 1; i >= 0; i--){
            res += 'a' + path[i] -> val;
        }
        return res;
    }
    
    void DFS(TreeNode* node){
        if (node == NULL) return;
        if (node -> left == NULL && node -> right == NULL){
            if (path.size() == 0){
                path = temp;
            }else{
                if (cmp(path, temp) >= 0){
                    path = temp;
                }
            }
            return;
        }
        if (node -> left){
            temp.push_back(node -> left);
            DFS(node -> left);
            temp.pop_back();
        }
        if (node -> right){
            temp.push_back(node -> right);
            DFS(node -> right);
            temp.pop_back();
        }
    }
    
    void reverse(vector<TreeNode*>& p){
        vector<TreeNode*> res;
        for (int i = p.size() - 1; i >= 0; i--)
            res.push_back(p[i]);
        p = res;
    }
   
    int cmp(vector<TreeNode*> p1, vector<TreeNode*> p2){
        // p1 < p2,return -1
        reverse(p1), reverse(p2);
        for (int i = 0; i < min(p1.size(), p2.size()); i++){
            if (p1[i] -> val < p2[i] -> val){
                return -1;
            }else if(p1[i] -> val > p2[i] -> val){
                return 1;
            }
        }
        if (p1.size() < p2.size()){
            return -1;
        }else if (p1.size() > p2.size()){
            return 1;
        }else{
            return 0;
        } 
    }
};

4. 区间列表的交集

two pointer扫一下所有的区间，求出所有的交集。

代码：

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
        vector<vector<int>> res;
        if (A.size() == 0 || B.size() == 0) return res;
        int l1 , r1, l2, r2;
        int i = 0, j = 0;
        while (i < A.size() && j < B.size()){
            l1 = A[i][0], r1 = A[i][1];
            l2 = B[j][0], r2 = B[j][1];
            intersect(l1, r1, l2, r2, res);
            if (r1 > r2){
                j++;
            }else if (r1 < r2){
                i++;
            }else {
                i++;
                j++;
            }
        }
        return res;
    }
    
    void intersect(int l1, int r1, int l2, int r2, vector< vector<int> >& res){
        vector<int> range(2);
        if (l2 > r1 || l1 > r2){
            return;
        }else{
            range[0] = max(l1, l2);
            range[1] = min(r1, r2);
        }
        res.push_back(range);
    }
};

5. 二叉树的垂序遍历

遍历二叉树记录每个结点的坐标，在同一横坐标下按从上到下的顺序输出（纵坐标递减）输出结点值，相同的纵坐标下按值从小到大输出。
代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
struct Node{
    int x, y, val;
    Node(int _x, int _y, int _val):x(_x), y(_y), val(_val){}
};
    
int mycmp(Node n1, Node n2){
    if (n1.y != n2.y)
        return n1.y > n2.y;
    return n1.val < n2.val;
}

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        vector<Node> nodes[2010];
        vector< vector<int> > res;
        DFS(make_pair(root, Node(1000, 0, root -> val)), nodes);
        for (int i = 0; i <= 2000; i++){
            if (nodes[i].size()){
                vector<int> vec;
                sort(nodes[i].begin(), nodes[i].end(), mycmp);
                for (int j = 0; j < nodes[i].size(); j++){
                    vec.push_back(nodes[i][j].val);
                }
                res.push_back(vec);
            }
        }
        return res;
    }
    
    void DFS(pair<TreeNode*, Node> pr, vector<Node> nodes[]){
        TreeNode* tnode = pr.first;
        Node node = pr.second;
        nodes[node.x].push_back(node);
        if (tnode -> left){
            Node newNode(node.x - 1, node.y - 1, tnode -> left -> val);
            DFS(make_pair(tnode -> left, newNode), nodes);
        }
        if (tnode -> right){
            Node newNode(node.x + 1, node.y - 1, tnode -> right -> val);
            DFS(make_pair(tnode -> right, newNode), nodes);
        }
    }
};