题目链接

https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree/

题解一

• 自己想的思路，只用了函数本身，没有用其它函数
• 根据题目给的下面2个条件，又因为树是递归结构，可得到：根节点、左子节点和右子节点中根节点是最小的。
  1. 每个节点的子节点数量只能为 2 或 0。
  2. 如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。
• 思路见代码和注释

// Problem: LeetCode 671
// URL: https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree/
// Tags: Tree Recursion
// Difficulty: Easy

#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
};

class Solution{
public:
    int findSecondMinimumValue(TreeNode* root) {
        // 如果节点为空或者无左右子树，则不存在第二小的节点
        if(root==nullptr || root->left==nullptr || root->right==nullptr)
            return -1;
        // 如果左右子节点的值相等
        if(root->left->val == root->right->val){
            // 求左右子树中第二小的节点的值
            int leftSecondMin = findSecondMinimumValue(root->left);
            int rightSecondMin = findSecondMinimumValue(root->right);
            // 左右子树中不存在第二小的节点，则这整棵树中都不存在第二小的节点
            if (leftSecondMin == -1 && rightSecondMin == -1)
                return -1;
            // 左子树中不存在第二小的节点而右子树中存在第二小的节点，则右子树中第二小的节点即这整棵树中第二小的节点
            if (leftSecondMin == -1)
                return rightSecondMin;
            // 右子树中不存在第二小的节点而左子树中存在第二小的节点，则左子树中第二小的节点即这整棵树中第二小的节点
            if (rightSecondMin == -1)
                return leftSecondMin;
            return min(leftSecondMin, rightSecondMin);
        }
        // 左子节点的值小于右子节点的值，而左子节点的值也等于根节点的值
        else if(root->left->val < root->right->val){
            int leftSecondMin = findSecondMinimumValue(root->left);
            // 左子树中不存在第二小的节点，则右子节点就是整棵树中第二小的节点
            if(leftSecondMin==-1)
                return root->right->val;
            else
                // 左子树中存在第二小的节点，则其和右子节点中值较小的节点就是整棵树中第二小的节点
                return min(leftSecondMin, root->right->val);
        }
        // 和上个情况相似，不再注释说明
        else{
            int rightSecondMin = findSecondMinimumValue(root->right);
            if (rightSecondMin == -1)
                return root->left->val;
            else
                return min(rightSecondMin, root->left->val);
        }
    }
};

题解二

• 其他人给的题解，速度很快
• 思路是：既然已经保证根节点的值最小，那就只需要遍历左右子树，遍历时一旦发现大于最小值的值（也就是第二小的值）就停止遍历并返回结果

// Problem: LeetCode 671
// URL: https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree/
// Tags: Tree Recursion
// Difficulty: Easy

#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
};

class Solution{
private:
    int helper(TreeNode* root, int rootMin){
        // 空树则无第二小的节点
        if (root==nullptr)
            return -1;
        // 如果找到大于最小值的值（第二小的值），则返回
        if (root->val > rootMin)
            return root->val;
        // 左右子树中第二小的值
        int leftSecondMin = helper(root->left, rootMin);
        int rightSecondMin = helper(root->right, rootMin);
        // 左子树中不存在第二小的值，则结果取决于右子树
        if (leftSecondMin == -1)
            return rightSecondMin;
        // 右子树中不存在第二小的值，则结果取决于右子树
        if (rightSecondMin == -1)
            return leftSecondMin;
        // 左右子树都存在第二小的值，则取两者中的较小值
        return min(leftSecondMin, rightSecondMin);
    }

public:
    int findSecondMinimumValue(TreeNode* root) {
        return helper(root, root->val);
    }
};

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!