672.二叉树中第二小的节点

发表于 | 分类于
字数统计: 464 | 阅读时长 ≈ 1

一、题目描述

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。

给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。

示例 1:

1
2
3
4
5
6
7
8
9
输入: 
    2
   / \
  2   5
     / \
    5   7

输出: 5
说明: 最小的值是 2 ，第二小的值是 5 。

示例 2:

1
2
3
4
5
6
7
输入: 
    2
   / \
  2   2

输出: -1
说明: 最小的值是 2, 但是不存在第二小的值。

二、题解

1.递归

1.1 思路

关键条件：根节点 <= 孩子节点。由此可得根节点为最小的节点。

如果两个孩子节点都大于根节点，则不向下递归，返回较小的值；

否则：即存在根节点 == 孩子节点的情况

  • 如果左孩子等于根节点，则在此处的孩子节点不存在比不存在第二小的节点，那么继续向下递归，寻找此子树中比根节点大的值，并返回这个值，并与右孩子比较
  • 如果右孩子等于根节点，同上
  • 如果有一个孩子大于根节点，则返回这个值，等于根节点的子树继续递归，不存在则返回 -1

1.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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int help(struct TreeNode *root, int min)
{
    if (root == NULL)
        return -1;
    if (root->val > min)
        return root->val;
    int l = help(root->left, min);
    int r = help(root->right, min);
    if (l == -1)
        return r;
    if (r == -1)
        return l;
    return l > r ? r : l;
}

int findSecondMinimumValue(struct TreeNode *root)
{
    if (root == NULL)
        return -1;
    return help(root, root->val);
}