ในบทช่วยสอนนี้ เราจะเรียนรู้วิธีค้นหาโหนดระดับคี่ที่ลึกที่สุดในไบนารีทรี
ซึ่งคล้ายกับการหาความลึกของไบนารีทรี ตรงนี้เราต้องมีเงื่อนไขอีกอย่างหนึ่งคือว่าระดับปัจจุบันเป็นเลขคี่หรือไม่
มาดูขั้นตอนการแก้ปัญหากัน
-
เริ่มต้นไบนารีทรีด้วยข้อมูลจำลอง
-
เขียนฟังก์ชันแบบเรียกซ้ำเพื่อค้นหาโหนดระดับคี่ที่ลึกที่สุดในไบนารีทรี
-
หากโหนดปัจจุบันเป็นโหนดปลายสุดและระดับเป็นคี่ ให้ส่งคืนระดับปัจจุบัน
-
มิฉะนั้นจะคืนค่าสูงสุดของโหนดด้านซ้ายและโหนดด้านขวาด้วยการเรียกฟังก์ชันแบบเรียกซ้ำ
-
-
พิมพ์โหนดระดับคี่ที่ลึกที่สุด
ตัวอย่าง
มาดูโค้ดกันเลย
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
struct Node* newNode(int data) {
struct Node* node = (struct Node*) malloc(sizeof(struct Node));
node->data = data;
node->left = node->right = NULL;
return node;
}
int oddLeafDepthInTree(struct Node *root, int level) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL && level % 2 == 1) {
return level;
}
return max(oddLeafDepthInTree(root->left, level + 1), oddLeafDepthInTree(root->right, level + 1));
}
int main() {
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->right->left = newNode(5);
root->right->right = newNode(6);
root->right->left->right = newNode(7);
root->right->right->right = newNode(8);
int level = 1, depth = 0;
cout << oddLeafDepthInTree(root, level) << endl;
return 0;
} ผลลัพธ์
หากคุณรันโค้ดด้านบน คุณจะได้ผลลัพธ์ดังต่อไปนี้
3
บทสรุป
หากคุณมีข้อสงสัยใดๆ ในบทแนะนำ โปรดระบุในส่วนความคิดเห็น
