LeetCode987(2021.7.31)

LC987. 二叉树的垂序遍历

/**
 * Definition for a binary tree node.
 * 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<vector<int>> verticalTraversal(TreeNode* root) {
        vector<tuple<int, int, int>> nodes;

        function<void(TreeNode*, int, int)> dfs = [&](TreeNode* node, int row, int col) {
            if (!node) return;
            nodes.emplace_back(col, row, node->val);
            dfs(node->left, row + 1, col - 1);
            dfs(node->right, row + 1, col + 1);
        };

        dfs(root, 0, 0);
        sort(nodes.begin(), nodes.end());
        vector<vector<int>> ans;
        int lastcol = INT_MIN;
        for (const auto& [col, row, value]: nodes) {
            if (col != lastcol) {
                lastcol = col;
                ans.emplace_back();
            }
            ans.back().push_back(value);
        }
        return ans;
    }
};

LeetCode1104(2021.7.29)

LC1104. 二叉树寻路

class Solution {
public:
    int getReverse(int label, int row) {
        return (1 << row - 1) + (1 << row) - 1 - label;
    }

    vector<int> pathInZigZagTree(int label) {
        int row = 1, rowStart = 1;
        while (rowStart * 2 <= label) {
            row++;
            rowStart *= 2;
        }
        if (row % 2 == 0) label = getReverse(label, row);

        vector<int> path;
        while (row > 0) {
            if (row % 2 == 0) path.push_back(getReverse(label, row));
            else path.push_back(label);
            row--;
            label >>= 1;
        }
        reverse(path.begin(), path.end());
        return path;
    }
};

LeetCode863(2021.7.28)

LC863. 二叉树中所有距离为 K 的结点

/**
 * 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 {
    unordered_map<int, TreeNode*> parents;
    vector<int> ans;

    void findParents(TreeNode* node) {
        if (node->left != nullptr) {
            parents[node->left->val] = node;
            findParents(node->left);
        }
        if (node->right != nullptr) {
            parents[node->right->val] = node;
            findParents(node->right);
        }
    }

    void findAns(TreeNode* node, TreeNode* from, int depth, int k) {
        if (node == nullptr) return;
        if (depth == k) {
            ans.push_back(node->val);
            return;
        }
        if (node->left != from) findAns(node->left, node, depth + 1, k);
        if (node->right != from) findAns(node->right, node, depth + 1, k);
        if (parents[node->val] != from) findAns(parents[node->val], node, depth + 1, k);
    }

public:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        findParents(root);
        findAns(target, nullptr, 0, k);
        return ans;
    }
};

LeetCode671(2021.7.27)

LC671. 二叉树中第二小的节点

/**
 * Definition for a binary tree node.
 * 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:
    int findSecondMinimumValue(TreeNode* root) {
        int ans = -1;
        int rootvalue = root->val;

        function<void(TreeNode*)> dfs = [&](TreeNode* node) {
            if (!node) return;
            if (ans != -1 && node->val >= ans) return;
            if (node->val > rootvalue) ans = node->val;
            dfs(node->left);
            dfs(node->right);
        };

        dfs(root);
        return ans;
    }
};

LeetCode1713(2021.7.26)

LC1713. 得到子序列的最少操作次数

class Solution {
public:
    int minOperations(vector<int> &target, vector<int> &arr) {
        int n = target.size();
        map<int, int> pos;
        for (int i = 0; i < n; ++i) pos[target[i]] = i;
        vector<int> d;
        for (int val : arr) {
            if (pos.count(val)) {
                int idx = pos[val];
                auto it = lower_bound(d.begin(), d.end(), idx);
                if (it != d.end()) *it = idx;
                else d.push_back(idx);
            }
        }
        return n - d.size();
    }
};

LeetCode1743(2021.7.25)

LC1743. 从相邻元素对还原数组

class Solution {
public:
    vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
        map<int, vector<int>> mp;
        for (auto& adjacentPair : adjacentPairs) {
            mp[adjacentPair[0]].push_back(adjacentPair[1]);
            mp[adjacentPair[1]].push_back(adjacentPair[0]);
        }

        int n = adjacentPairs.size() + 1;
        vector<int> ret(n);
        for (auto& [e, adj] : mp) {
            if (adj.size() == 1) {
                ret[0] = e;
                break;
            }
        }

        ret[1] = mp[ret[0]][0];
        for (int i = 2; i < n; i++) {
            auto& adj = mp[ret[i - 1]];
            ret[i] = ret[i - 2] == adj[0] ? adj[1] : adj[0];
        }
        return ret;
    }
};

LeetCode138(2021.7.22)

LC138. 复制带随机指针的链表

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    map<Node*, Node*> cachedNode;

    Node* copyRandomList(Node* head) {
        if (head == nullptr) return head;
        if (!cachedNode.count(head)) {
            Node* headNew = new Node(head->val);
            cachedNode[head] = headNew;
            headNew->next = copyRandomList(head->next);
            headNew->random = copyRandomList(head->random);
        }
        return cachedNode[head];
    }
};