C++ 中二叉树的次小节点

假设存在一个非空的特殊二叉树，其中包含一些非负值，树中的每个节点正好有两个或零个子节点。如果节点有两个子节点，则该节点的值是其两个子节点中较小的值。换句话说，我们可以说 [root.val = root.left.val 和 root.right.val 中的最小值]。如果我们有这样的二叉树，我们需要找到由整个树中所有节点的值组成的集合中的次小值。如果没有这样的元素，则返回 -1。

因此，如果输入如下所示：

则输出将为 5。最小值为 2，次小值为 5。

为了解决这个问题，我们将遵循以下步骤：

• 定义一个函数 TraverseNodes()，它将接收节点、最小值和次小值作为参数。
• 如果节点为空，则：
  • 返回
• 如果节点的值大于最小值，则：
  • 如果次小值等于 -1 或节点的值小于次小值，则：
    • 次小值 := 节点的值
• TraverseNodes(节点的左子节点，最小值，次小值)
• TraverseNodes(节点的右子节点，最小值，次小值)
• 在主方法中执行以下操作：
• 最小值 := 根节点的值（如果根节点不为空，否则为 -1）
• 次小值 := -1
• TraverseNodes(根节点，最小值，次小值)
• 返回次小值

让我们看一下以下实现，以便更好地理解：

示例

 实时演示

#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

Arnab Chakraborty

更新于： 2020-07-04

521 次查看

开启您的 职业生涯

通过完成课程获得认证

立即开始