Mind palace

some thoughts

0%

742. Closest Leaf in a Binary Tree

Posted on Edited on In Disqus:
Symbols count in article: 3.5k Reading time ≈ 3 mins.

O(n) time O(n) space
跟863. All Nodes Distance K in Binary Tree类似
把树转成图再bfs找最近端点，如果只有k一个点，则图为空，返回k，如果k只有一个邻居且k不是根，则k一定是叶子，返回k，如果图中某个『最近』端点不是根，返回该点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * 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:
    int findClosestLeaf(TreeNode* root, int k) {
        unordered_map<int, unordered_set<int>> g;
        createGraph(root, g);
        if (g.empty() || g[k].size() == 1 && root->val != k) return k; // 如果k自己是leaf那就是他自己
        queue<int> q;
        q.push(k);
        while (!q.empty()) {
            int p = q.front(); q.pop();
            if (g[p].empty() && root->val != p) return p; // 没有邻居说明之前邻居已经把它从我的邻居里删除，我是根或者叶，如果我不是根，则返回我
            for (auto n : g[p]) {
                q.push(n);
                g[n].erase(p); // 从邻居那移除我，防止邻居继续访问我
            }
        }
        return k;
    }

    void createGraph(TreeNode *root, unordered_map<int, unordered_set<int>> &g) {
        if (!root) return;
        if (root->left) {
            g[root->val].insert(root->left->val);
            g[root->left->val].insert(root->val);
            createGraph(root->left, g);
        }
        if (root->right) {
            g[root->val].insert(root->right->val);
            g[root->right->val].insert(root->val);
            createGraph(root->right, g);
        }
    }
};

WA!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/**
 * 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:
    int findClosestLeaf(TreeNode* root, int k) {
        int k2root = 10000;
        auto K = searchK(root, k, 0, k2root);
        int other2root = 10000;
        auto other = searchOther(root, k, other2root);
        int child2k = 10000;
        auto child = searchKTree(K, child2k);
        return k2root + other2root < child2k ? other->val : child->val;
    }

    TreeNode *searchK(TreeNode *root, int k, int lvl, int &k2root) {
        if (!root) return root;
        if (root->val == k) {
            k2root = lvl;
            return root;
        }
        auto l = searchK(root->left, k, lvl + 1, k2root);
        if (l && l->val == k) {
            return l;
        }
        auto r = searchK(root->right, k, lvl + 1, k2root);
        if (r && r->val == k) {
            return r;
        }
        return nullptr;
    }

    TreeNode *searchKTree(TreeNode *K, int &child2k) {
        TreeNode *res = nullptr;
        queue<pair<TreeNode *, int>> q;
        q.emplace(K, 0);
        while (!q.empty() && child2k == 10000) {
            auto curr = q.front().first;
            int lvl = q.front().second;
            q.pop();
            if (!curr->left && !curr->right) {
                if (lvl < child2k) {
                    child2k = lvl;
                    res = curr;
                    break;
                }
            } else if (!curr->left) {
                q.emplace(curr->right, lvl + 1);
            } else if (!curr->right) {
                q.emplace(curr->left, lvl + 1);
            } else {
                q.emplace(curr->left, lvl + 1);
                q.emplace(curr->right, lvl + 1);
            }
        }
        return res;
    }

    TreeNode *searchOther(TreeNode *root, int k, int &other2root) {
        queue<pair<TreeNode *, int>> q;
        q.emplace(root, 0);
        TreeNode *res = nullptr;
        while (!q.empty() && other2root == 10000) {
            auto curr = q.front().first;
            int lvl = q.front().second;
            q.pop();
            if (curr->val == k) continue;
            if (!curr->left && !curr->right) {
                if (lvl < other2root) {
                    other2root = lvl;
                    res = curr;
                    break;
                }
            } else if (!curr->left) {
                q.emplace(curr->right, lvl + 1);
            } else if (!curr->right) {
                q.emplace(curr->left, lvl + 1);
            } else {
                q.emplace(curr->left, lvl + 1);
                q.emplace(curr->right, lvl + 1);
            }
        }
        return res;
    }
};