首页 > 编程语言 >leetcode 671. Second Minimum Node In a Binary Tree

leetcode 671. Second Minimum Node In a Binary Tree

时间:2023-05-30 17:37:33浏览次数:47  
标签:Node Binary right node val Tree value root left

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.

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.

Example 1:

Input: 
    2
   / \
  2   5
     / \
    5   7

Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.

Example 2:

Input: 
    2
   / \
  2   2

Output: -1
Explanation: The smallest value is 2, but there isn't any second smallest value.

不是二叉搜索树!当心,必须要过完所有的结点才知道答案!
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def findSecondMinimumValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        inf = float('inf')
        min1, min2 = inf, inf       
        # min1 < min2
        
        def dfs(node):
            nonlocal min1, min2
            if not node: return            
            dfs(node.left)  
            if node.val != min1 and node.val != min2:
                if node.val < min1:
                    min2 = min1
                    min1 = node.val
                elif node.val < min2:
                    min2 = node.val
            dfs(node.right)
        
        assert root
        dfs(root)
        return min2 if min2 != inf else -1

 貌似我理解题目错了。

Based on the special property of the tree, we can guarantee that the root node is the smallest node in the tree.

- Yangshun

class Solution(object):
    def findSecondMinimumValue(self, root):
        res = [float('inf')]
        def traverse(node):
            if not node:
                return
            if root.val < node.val < res[0]:
                res[0] = node.val
            traverse(node.left)
            traverse(node.right)
        traverse(root)
        return -1 if res[0] == float('inf') else res[0]

 

学到闭包写法!如果不使用nonlocal的话!

 

类似我这样直接暴力,只是没有利用root信息:

def findSecondMinimumValue(self, root):
    self.ans = float('inf')
    min1 = root.val

    def dfs(node):
        if node:
            if min1 < node.val < self.ans:
                self.ans = node.val
            elif node.val == min1:
                dfs(node.left)
                dfs(node.right)

    dfs(root)
    return self.ans if self.ans < float('inf') else -1

 

 

还有就是常规的思路:

public int findSecondMinimumValue(TreeNode root) {
    if (root == null) {
        return -1;
    }
    if (root.left == null && root.right == null) {
        return -1;
    }
    
    int left = root.left.val;
    int right = root.right.val;
    
    // if value same as root value, need to find the next candidate
    if (root.left.val == root.val) {
        left = findSecondMinimumValue(root.left);
    }
    if (root.right.val == root.val) {
        right = findSecondMinimumValue(root.right);
    }
    
    if (left != -1 && right != -1) {
        return Math.min(left, right);
    } else if (left != -1) {
        return left;
    } else {
        return right;
    }
}

 

public int findSecondMinimumValue(TreeNode root) 
{
    int rootVal = root.val;
    int secondSmall =Integer.MAX_VALUE;
    boolean diffFound = false;
    Queue<TreeNode> Q= new LinkedList<TreeNode>();
    Q.add(root);

    while(!Q.isEmpty())
    {
        TreeNode curr=Q.poll();
        if(curr.val!=rootVal && curr.val < secondSmall)
        {
            secondSmall=curr.val;
            diffFound=true;
        }
        if(curr.left!=null)
        {
            Q.add(curr.left);
            Q.add(curr.right);
        }
    }

    return (secondSmall == Integer.MAX_VALUE && !diffFound) ? -1 : secondSmall;
}

 

标签:Node,Binary,right,node,val,Tree,value,root,left
From: https://blog.51cto.com/u_11908275/6380972

相关文章

  • leetcode 107. Binary Tree Level Order Traversal II
    Givenabinarytree,returnthebottom-uplevelordertraversalofitsnodes'values.(ie,fromlefttoright,levelbylevelfromleaftoroot).Forexample:Givenbinarytree[3,9,20,null,null,15,7],3/\920/\157returnits......
  • leetcode 101. Symmetric Tree
    Givenabinarytree,checkwhetheritisamirrorofitself(ie,symmetricarounditscenter).Forexample,thisbinarytree[1,2,2,3,4,4,3]issymmetric:1/\22/\/\3443Butthefollowing[1,2,2,null,3,null,3]isnot:1/\2......
  • 在node项目中使用log4.js记录日志
    1.在项目根目录创建保存日志文件的文件夹logs2.修改.gitignore文件,添加logs文件夹,这样使用git提交进忽略logs文件夹。node_modules.envlogs3.在config文件夹下新增log4j.js文件保存log4js的配置,路径:./src/config/log4j.js//config.jsletpath=require('pat......
  • 2023-05-30 前端通过node获取七牛云的token(token最好还是在后端返回,前端获取token会暴
    constfs=require('fs');constqiniu=require('qiniu');varaccessKey='你的accessKey';varsecretKey='你的secretKey';varmac=newqiniu.auth.digest.Mac(accessKey,secretKey);//获取七牛tokenvaroptions={......
  • nacos服务下线操作时报错:The Raft Group [naming_instance_metadata] did not find th
    【问题描述】caused:errCode:500,errMsg:dometadataoperationfailed;caused:com.alibaba.nacos.consistency.exception.ConsistencyException:TheRaftGroup[naming_instance_metadata]didnotfindtheLeadernode;caused:TheRaftGroup[naming_instance_metad......
  • 2023-05-30 浅试nodejs实现登录接口业务(未完,待测试)
    constexpress=require('express');constbodyParser=require('body-parser');constmysql=require('mysql');//创建MySQL连接池constpool=mysql.createPool({host:'localhost',user:'root',password......
  • linux Centos7 部署 nodejs服务
    nodejs服务要有nodejs环境。所以要先安装nodejs不会安装的可以看  Centos7安装npm学习 安装pm2cnpminstallpm2-g,查看pm2是否安装成功pm2-v,如果报错,升级node版本进入node项目目录,安装项目依赖 cnpminstall创建pm2任务 [root@localhostserver]#pm2sta......
  • Nodejs版本控制
    Nodejs版本控制NVM全称node.jsversionmanagement,专门针对node版本进行管理的工具,通过它可以安装和切换不同版本的node.js下载地址:https://github.com/coreybutler/nvm-windows下载之后安装的时候注意不能有中文名字中文路径以及空格可以显示当前的node版本nvmlist......
  • java treemap
    TreeMap是Java中的一个类,它实现了Map接口,利用红黑树数据结构来有序存储键值对。TreeMap中的键按升序排序,若要自定义排序方式,则可以提供自定义的比较器。TreeMap实现了高效的数据访问、插入和删除操作,大多数常规操作的时间复杂度为O(logn)。importjava.util.TreeMap;public......
  • UE5 custom node随笔
    前言UE蓝图的customnode不像unity一样灵活,且貌似因为渲染框架的更改4.2之前使用customnode的方式和如今大不相同,经过捣鼓一番总算是知道如何使用,本篇会介绍如何使用customnodeCode主要问题在于customnode的Code处,在UE4.2时以前使用方式是在你的项目下新建Shaders文件夹......