หาโหนดลำดับที่ k ในการทะลุแนวทแยงของต้นไม้แบบทวิภาคใน C++

ในบทช่วยสอนนี้ เราจะเขียนโปรแกรมเพื่อหาโหนดลำดับที่ k ในการทะลุแนวทแยง (diagonal traversal) ของต้นไม้แบบทวิภาค

ขั้นตอนการแก้ปัญหา

• กำหนดค่าเริ่มต้นของต้นไม้แบบทวิภาคด้วยข้อมูลตัวอย่าง
• กำหนดค่าเริ่มต้นของตัวเลข k
• ทะลุต้นไม้แบบทวิภาคแบบแนวทแยงโดยใช้โครงสร้างข้อมูล queue
  • ลดค่า k ลงทีละโหนด
  • คืนค่าโหนดเมื่อ k กลายเป็น 0
• คืนค่า -1 ถ้าไม่มีโหนดดังกล่าว

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

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

struct Node { 
    int data; 
    Node *left, *right; 
}; 

Node* getNewNode(int data) { 
    Node* node = (Node*)malloc(sizeof(Node)); 
    node->data = data; 
    node->left = node->right = NULL; 
    return node; 
} 

int findDiagonalKthElement(Node* root, int k) { 
    if (root == NULL || k == 0) { 
        return -1; 
    } 
    int result = -1; 
    queue<Node*> q; 
    q.push(root); 
    q.push(NULL); 
    while (!q.empty()) { 
        Node* temp = q.front(); 
        q.pop(); 
        if (temp == NULL) { 
            if (q.empty()) { 
                if (k == 0) { 
                    return result; 
                } else { 
                    break; 
                } 
            } 
            q.push(NULL); 
        } else { 
            while (temp) { 
                if (k == 0) { 
                    return result; 
                } 
                k--; 
                result = temp->data; 
                if (temp->left) { 
                    q.push(temp->left); 
                } 
                temp = temp->right; 
            } 
        } 
    } 
    return -1; 
} 

int main() { 
    Node* root = getNewNode(10); 
    root->left = getNewNode(5); 
    root->right = getNewNode(56); 
    root->left->left = getNewNode(3); 
    root->left->right = getNewNode(22); 
    root->right->right = getNewNode(34); 
    root->right->right->left = getNewNode(45); 
    root->left->right->left = getNewNode(67); 
    root->left->right->right = getNewNode(100); 
    int k = 9; 
    cout << findDiagonalKthElement(root, k) << endl; 
    return 0; 
}

ผลลัพธ์

หากรันโค้ดด้านบน จะได้ผลลัพธ์ดังนี้:

67

สรุป

หากมีข้อสงสัยเกี่ยวกับบทช่วยสอนนี้ สามารถถามได้ในส่วนความคิดเห็น