[数据结构与算法]7-28每日一题：第k个除数 二叉树中所有距离为K的结点

Acwing第k个除数

思路

试除法求所有约数，对约数排序
时间复杂度：$O(\sqrt{n}logn)$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long LL;
LL n, k;
int main()
{
    cin >> n >> k;
    vector<LL> d;
    for (LL i = 1; i * i <= n; i ++ )
    {
        if (n % i == 0)
        {
            d.push_back(i);
            if (n / i != i) d.push_back(n / i);
        }
    }
    if (k > d.size()) puts("-1");
    else 
    {
        nth_element(d.begin(),d.begin() + k - 1,d.end());
        // sort(d.begin(),d.end());
        cout << d[k - 1] << endl;
    }
    return 0;
}

Leetcode每日一题：二叉树中所有距离为K的结点

思路：

遍历，保存每个结点的父节点$O(n)$
从$target$开始搜索直到深度为$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*> pa;
    vector<int> res;

    void find_parents(TreeNode* root)
    {
        if (root == nullptr)
            return ;
        if (root->left)
        {
            pa[root->left->val] = root;
            find_parents(root->left);
        }

        if (root->right)
        {
            pa[root->right->val] = root;
            find_parents(root->right);
        }
    }

    void dfs(TreeNode* node, TreeNode* from, int depth, int k)
    {
        if (node == nullptr) 
            return ;
        if (depth == k)
        {
            res.push_back(node->val);
            return ;
        }
        if (node->left != from)
            dfs(node->left, node, depth + 1, k);
        if (node->right != from)
            dfs(node->right, node, depth + 1, k);
        if (pa[node->val] != from)
            dfs(pa[node->val], node, depth + 1, k);
    }
public:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
       find_parents(root);

       dfs(target, nullptr, 0, k);

       return res; 
    }
};