Nút tối thiểu thứ hai trong cây nhị phân trong C ++

Giả sử có một cây nhị phân đặc biệt không rỗng với một giá trị nào đó không âm, ở đây mỗi nút trong cây này có đúng hai hoặc không con. Nếu nút có hai nút con, thì giá trị của nút này là giá trị nhỏ hơn trong số hai nút con của nó. Nói cách khác, chúng ta có thể nói rằng [root.val =tối thiểu của root.left.val, root.right.val]. Nếu chúng ta có cây nhị phân như vậy, chúng ta phải tìm giá trị nhỏ nhất thứ hai trong tập được tạo thành từ giá trị của tất cả các nút trong toàn bộ cây. Nếu không có phần tử như vậy, hãy trả về -1 để thay thế.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 5. Giá trị nhỏ nhất là 2, giá trị nhỏ nhất thứ hai là 5.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm TraverseNodes (), hàm này sẽ lấy node, min, nextMin,
• nếu nút là null, thì -
  • trở lại
• nếu val của nút> min, thì -
  • nếu nextMin giống -1 hoặc val của nút
  • nextMin:=val của nút

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
class Solution {
public:
   int findSecondMinimumValue(TreeNode* root) {
      int min = (root && root->val != 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);
   }
};
main(){
   Solution ob;
   vector<int> v = {2,2,5,NULL,NULL,5,7};
   TreeNode *root = make_tree(v);
   cout << (ob.findSecondMinimumValue(root));
}

Đầu vào

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

Đầu ra

5