[leetcode]Second Minimum Node In a Binary Tree c++

原题&翻译

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node's value is the smaller value among its two sub-nodes.

给出一个不为空的特殊二叉树,这个二叉树节点都为非负数,且其一定有 2 个子节点或没有子节点。任何一个有两个子节点的节点,其所包含的值,一定和这两个子节点中较小的一个值相同。

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes' value in the whole tree.

这样的二叉树给出,你需要输出整棵树中第二小的值。

If no such second minimum value exists, output -1 instead.

如果没有这样的值,返回 -1。

例子 1:

输入 :

    2
   / \
  2   5
     / \
    5   7

输出 : 5
分析: 最小的值为 2,第二小的值为 5.

例子 2:

输入:

    2
   / \
  2   2

输出: -1
分析: 最小值为 2,没有第二小的值。


解体思路

无视特殊二叉树的说法,当作普通树暴力计算。
稍微注意一点,递归里面局部变量毫无意义,全局变量才是王道,当然,我这已经属于滥用全局变量了。

class Solution {
public:
    int min1 = INT_MAX;
    int min2 = INT_MAX;
    int findSecondMinimumValue(TreeNode* root) {
        if(root->val <= min1){
            min1 = root->val;
        }else if(root->val < min2){
            min2 = root->val;
        }
        if(root->left) findSecondMinimumValue(root->left);
        if(root->right) findSecondMinimumValue(root->right);
        return (min1==min2 || min2==INT_MAX)?-1:min2;
    }
};

方法二

这个方法利用了本二叉树的特殊性:
1. 要么没有子树,要么有两个。
2. 根一定是最小的一个。
判断左右节点是否不等,不等则返回大的一方;相等则继续递归,直到穷尽。

class Solution {
public:
    int findSecondMinimumValue(TreeNode* root) {
        if(root->left == NULL) return -1;
        int l = root->left->val > root->right->val ? root->left->val : findSecondMinimumValue(root->left);
        int r = root->right->val > root->left->val ? root->right->val : findSecondMinimumValue(root->right);
        if (l == -1) return r;
        if (r == -1) return l;
        return min(l,r);
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注