All Nodes Distance K in Binary Tree – หาโหนดระยะ K จากเป้าหมายใน C++

ปัญหา: All Nodes Distance K in Binary Tree

กำหนด Binary Tree, โหนดเป้าหมาย (target), และจำนวนเต็ม K หา ค่าของโหนดทั้งหมดที่มีระยะห่าง K จาก target

ระยะห่าง = จำนวนขอบ (edges) ในเส้นทาง

ตัวอย่าง

Tree: [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2

Output: [7, 4, 1]

        3
       / \
      5   1
     / \ / \
    6  2 0 8
      / \
     7   4

ระยะ 2 จากโหนด 5: โหนด 7, 4 (ลูกของ 2) และ 1 (พี่น้องของ 5)

แนวทางแก้ปัญหา: Graph + BFS

ข้อสังเกต

Tree ไม่มี pointer ไป parent → ต้องสร้าง parent map ก่อน แล้วค่อย BFS จาก target 3 ทิศทาง (left, right, parent)

ขั้นตอน

1. DFS สร้าง parent map – วนทุกโหนด บันทึก parent ของแต่ละโหนด
2. BFS จาก target – เริ่มที่ (target, level=0)
   • ถ้า level == K → เพิ่มค่าโหนดในคำตอบ
   • push เพื่อนบ้านที่ยังไม่ visited: left, right, parent
   • level + 1 ต้อง ≤ K
3. คืนรายการคำตอบ

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
    unordered_map<TreeNode*, TreeNode*> parent;

    void dfs(TreeNode* node, TreeNode* par = nullptr) {
        if (!node) return;
        parent[node] = par;
        dfs(node->left, node);
        dfs(node->right, node);
    }

public:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        parent.clear();
        dfs(root);

        vector<int> ans;
        queue<pair<TreeNode*, int>> q;
        unordered_set<TreeNode*> visited;

        q.emplace(target, 0);
        visited.insert(target);

        while (!q.empty()) {
            auto [node, level] = q.front(); q.pop();

            if (level == k) {
                ans.push_back(node->val);
                continue; // ไม่ต้องขยายต่อ
            }

            if (node->left && !visited.count(node->left)) {
                visited.insert(node->left);
                q.emplace(node->left, level + 1);
            }
            if (node->right && !visited.count(node->right)) {
                visited.insert(node->right);
                q.emplace(node->right, level + 1);
            }
            if (parent[node] && !visited.count(parent[node])) {
                visited.insert(parent[node]);
                q.emplace(parent[node], level + 1);
            }
        }
        return ans;
    }
};

การสร้าง Tree สำหรับทดสอบ

TreeNode* buildTree(vector<int> v) {
    if (v.empty()) return nullptr;
    TreeNode* root = new TreeNode(v[0]);
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (!q.empty() && i < v.size()) {
        TreeNode* cur = q.front(); q.pop();
        if (i < v.size() && v[i] != -1) {
            cur->left = new TreeNode(v[i]);
            q.push(cur->left);
        }
        i++;
        if (i < v.size() && v[i] != -1) {
            cur->right = new TreeNode(v[i]);
            q.push(cur->right);
        }
        i++;
    }
    return root;
}

int main() {
    Solution ob;
    vector<int> v = {3,5,1,6,2,0,8,-1,-1,7,4}; // -1 = null
    TreeNode* root = buildTree(v);
    TreeNode* target = root->left; // node 5
    auto ans = ob.distanceK(root, target, 2);
    for (int x : ans) cout << x << ' '; // 7 4 1
    return 0;
}

ความซับซ้อน

• เวลา: O(N) – DFS ทุกโหนด 1 ครั้ง, BFS ทุกโหนด 1 ครั้ง
• พื้นที่: O(N) – parent map, visited set, queue

ข้อสังเกต

• LeetCode 863 – ปัญหา Tree + Graph แปลง
• ใช้ unordered_map และ unordered_set ด้วย pointer ตรงๆ (hash ของ pointer)
• กรณี K = 0 → คืน [target->val] ได้ทันที