C++의 이진 트리에서 두 번째 최소 노드

음수가 아닌 값을 가진 비어 있지 않은 특수 이진 트리가 있다고 가정합니다. 여기에서 이 트리의 각 노드에는 정확히 2개 또는 0개의 자식이 있습니다. 노드에 두 개의 자식이 있는 경우 이 노드의 값은 두 자식 중 작은 값입니다. 즉, [root.val =root.left.val, root.right.val의 최소값]이라고 말할 수 있습니다. 이러한 이진 트리가 있으면 전체 트리에서 모든 노드의 값으로 구성된 집합에서 두 번째 최소값을 찾아야 합니다. 그러한 요소가 없으면 대신 -1을 반환합니다.

따라서 입력이 다음과 같으면

그러면 출력은 5가 됩니다. 가장 작은 값은 2이고 두 번째로 작은 값은 5입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• TraverseNodes() 함수를 정의합니다. 여기에는 node, min, nextMin이 필요합니다.
• 노드가 null이면 -
  • 반환
• 노드의 val> min이면 -
  • nextMin이 -1 또는 노드
  • nextMin :=노드의 값

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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));
}

입력

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

출력

5