离得最近的叶节点

离某值节点最近的叶节点

https://leetcode.com/problems/closest-leaf-in-a-binary-tree/

Given a binary tree where every node has a unique value, and a target key k, find the value of the nearest leaf node to target k in the tree.

Here, nearest to a leaf means the least number of edges travelled on the binary tree to reach any leaf of the tree. Also, a node is called a leaf if it has no children.

In the following examples, the input tree is represented in flattened form row by row. The actual root tree given will be a TreeNode object.

Example 1:
Input:
root = [1, 3, 2], k = 1
Diagram of binary tree:
          1
         / \
        3   2

Output: 2 (or 3)

Explanation: Either 2 or 3 is the nearest leaf node to the target of 1.
Example 2:
Input:
root = [1], k = 1
Output: 1

Explanation: The nearest leaf node is the root node itself.
Example 3:
Input:
root = [1,2,3,4,null,null,null,5,null,6], k = 2
Diagram of binary tree:
             1
            / \
           2   3
          /
         4
        /
       5
      /
     6

Output: 3
Explanation: The leaf node with value 3 (and not the leaf node with value 6) is nearest to the node with value 2.
Note:

root represents a binary tree with at least 1 node and at most 1000 nodes.

Every node has a unique node.val in range [1, 1000].

There exists some node in the given binary tree for which node.val == k.

int findClosestLeaf(TreeNode* root, int k) {
    // 题目：树中有一个节点值为k，找出离这个节点最近的叶节点值
    // 可沿边上下运动，其实就是把这树当作无向图，用bfs找最短路径

    // 先dfs创建无向图，同时找出k节点（用后序遍历）
    unordered_map<TreeNode *, vector<TreeNode *>> adj;
    auto theKNode = dfs(root, k, adj);

    queue<TreeNode *> q;
    q.push(theKNode);
    unordered_set<TreeNode *> visited;
    visited.insert(theKNode);

    while (!q.empty()) {
        auto u = q.front(); q.pop();
        if (!u->left && !u->right) return u->val;

        for (auto v : adj[u]) {
            if (visited.count(v)) continue;
            q.push(v);
            visited.insert(v);
        }
    }
    return INT_MIN;
}

TreeNode* dfs(TreeNode *root, int k, unordered_map<TreeNode *, vector<TreeNode *>> &adj) {
    if (!root) return NULL;
    if (root->left) {
        adj[root].push_back(root->left);
        adj[root->left].push_back(root);
    }
    if (root->right) {
        adj[root].push_back(root->right);
        adj[root->right].push_back(root);
    }
    auto left = dfs(root->left, k, adj);
    auto right = dfs(root->right, k, adj);
    if (left) return left; // 在左子树中找到k节点
    if (right) return right;
    if (root->val == k) return root;
    return NULL;
}

algo-aha

离某值节点最近的叶节点