LeetCode671二叉树中第二小的结点

Posted on | | Visitors:
Words count in article: 959 字 | Reading time ≈ 4 分

题目链接

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

题解一

  • 自己想的思路，只用了函数本身，没有用其它函数
  • 根据题目给的下面2个条件，又因为树是递归结构，可得到：根结点、左子结点和右子结点中根结点是最小的。
    1. 每个结点的子结点数量只能为 2 或 0。
    2. 如果一个结点有两个子结点的话，那么该结点的值等于两个子结点中较小的一个。
  • 思路见代码和注释
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// 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);
        }
    }
};

题解二

  • 其他人给的题解，速度很快
  • 思路是：既然已经保证根结点的值最小，那就只需要遍历左右子树，遍历时一旦发现大于最小值的值（也就是第二小的值）就停止遍历并返回结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 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/

欢迎讨论和交流!