【力扣】671. 二叉树中第二小的节点

vlambda
2021-08-08

【力扣】671. 二叉树中第二小的节点

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

七月

难度：简单

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

题目

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

更正式地说， root.val = min(root.left.val, root.right.val) 总成立。

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

示例

【力扣】671. 二叉树中第二小的节点

输入：root = [2,2,5,null,null,5,7]

输出：5

解释：最小的值是 2 ，第二小的值是 5 。

【力扣】671. 二叉树中第二小的节点

输入：root = [2,2,2]

输出：-1

解释：最小的值是 2, 但是不存在第二小的值。

 
   
   
 
  
    
    
   
    
     
     
 
     
     
      
      
 
      
      
      提示
 
      
      
      
 
      
     
     
     
 
     
    
  
 
   
   
 


 
   
   
 
  
    
    
  树中节点数目在范围 [1, 25] 内
  
    
    
  1 <= Node.val <= 231 - 1
  
    
    
  对于树中每个节点 root.val == min(root.left.val, root.right.val)


 
   
   
 
 
   
   
 
  
    
    
   
    
     
     
 
     
     
      
      
 
      
      
      题目分析
 
      
      
      
 
      
     
     
     
 
     
    
  
 
   
   
 


 
   
   
 
  
    
    
  这个题可以转换为求左右子树的最小节点。

  
    
    
  考虑到节点数较少，也可以全部遍历排序再找第二小。


 
   
   
 
 
   
   
 
  
    
    
   
    
     
     
 
     
     
      
      
 
      
      
      解题
 
      
      
      
 
      
     
     
     
 
     
    
  
 
   
   
 
 
   
   
 
  
    
    
   
    
     
      
       
       
 
       
      
     
    
  
 
   
   
 
‍‍‍‍
 
   
   
 
  
    
    
   
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
  
  
    
    
  class Solution { public: int findSecondMinimumValue(TreeNode* root) { if(root==nullptr||root->left==nullptr) return -1; int r = root->right->val; int l = root->left->val; if(root->left->val > root->right->val){ r = findSecondMinimumValue(root->right); } else if(root->left->val < root->right->val){ l = findSecondMinimumValue(root->left); } else { r = findSecondMinimumValue(root->right); l = findSecondMinimumValue(root->left); } if(l == -1 && r==-1) return -1; else if(l==-1) return r; else if(r==-1) return l; else return min(l,r); }};
 
   
   
 


 
   
   
 
  
    
    
   
    
     
      
       
        
        你每日一题了吗？ 
        
       
      
      
       
        
        欢迎评论区打卡、指正喔～～