home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

โหนดที่สองที่น้อยที่สุดใน Binary Tree ใน C++

ปัญหา

สมมติว่ามี binary tree พิเศษที่ไม่ว่างเปล่า มีค่าที่ไม่เป็นลบ แต่ละโหนดในต้นไม้นี้มีลูกสองคนหรือไม่มีลูกเลย หากโหนดมีลูกสองคน ค่าของโหนดนั้นจะเป็นค่าน้อยกว่าระหว่างลูกสองคนนั้น กล่าวอีกนัยหนึ่ง root.val = min(root.left.val, root.right.val) หากเรามี binary tree แบบนี้ เราต้องหาค่าที่สองน้อยที่สุดในเซ็ตที่สร้างจากค่าของโหนดทั้งหมดในต้นไม้ทั้งต้น หากไม่มีสมาชิกแบบนั้น ให้คืนค่า -1 แทน

เช่น ถ้าผนวกเข้าเป็น (รูปภาพต้นไม้) ผลลัพธ์จะเป็น 5 ค่าที่น้อยที่สุดคือ 2 ค่าที่สองน้อยที่สุดคือ 5

วิธีแก้ปัญหา

  1. กำหนดฟังก์ชัน TraverseNodes() รับ node, min, nextMin:
    • ถ้า node เป็น null: คืนค่า
    • ถ้าค่าของ node > min:
      • ถ้า nextMin เท่ากับ -1 หรือค่าของ node < nextMin: nextMin := ค่าของ node
    • TraverseNodes(left of node, min, nextMin)
    • TraverseNodes(right of node, min, nextMin)
  2. จากเมธอดหลัก:
    • min := ค่าของ root ถ้า root ไม่เป็น null มิฉะนั้น -1
    • nextMin := -1
    • TraverseNodes(root, min, nextMin)
    • คืนค่า nextMin

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

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

class TreeNode{ 
public: 
    int val; 
    TreeNode *left, *right; 
    TreeNode(int data){ 
        val = data; 
        left = NULL; 
        right = NULL; 
    } 
}; 

void insert(TreeNode **root, int val){ 
    queue<TreeNode*> q; 
    q.push(*root); 
    while(q.size()){ 
        TreeNode *temp = q.front(); 
        q.pop(); 
        if(!temp->left){ 
            if(val != NULL) 
                temp->left = new TreeNode(val); 
            else 
                temp->left = new TreeNode(0); 
            return; 
        }else{ 
            q.push(temp->left); 
        } 
        if(!temp->right){ 
            if(val != NULL) 
                temp->right = new TreeNode(val); 
            else 
                temp->right = new TreeNode(0); 
            return; 
        }else{ 
            q.push(temp->right); 
        } 
    } 
} 

TreeNode *make_tree(vector<int> v){ 
    TreeNode *root = new TreeNode(v[0]); 
    for(int i = 1; ival != 0) ? root->val : -1; 
        int nextMin = -1; 
        TraverseNodes(root, min, nextMin); 
        return nextMin; 
    } 

    void TraverseNodes(TreeNode* node, int min, int& nextMin) { 
        if (!node || node->val == 0) { 
            return; 
        } 
        if (node->val > min) { 
            if (nextMin == -1 || node->val < nextMin) { 
                nextMin = node->val; 
            } 
        } 
        TraverseNodes(node->left, min, nextMin); 
        TraverseNodes(node->right, min, nextMin); 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<int> v = {2,2,5,NULL,NULL,5,7}; 
    TreeNode *root = make_tree(v); 
    cout << (ob.findSecondMinimumValue(root)); 
}

อินพุต

{2,2,5,NULL,NULL,5,7}

เอาต์พุต

5