Java实现 LeetCode 671 二叉树中第二小的节点（遍历树）

爱被打了一巴掌 2023-07-22 03:48 38阅读 0赞

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

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

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

示例 1:

输入: 
        2
       / \
      2   5
         / \
        5   7
    
    输出: 5

说明: 最小的值是 2 ，第二小的值是 5 。  
示例 2:

输入: 
        2
       / \
      2   2
    
    输出: -1

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

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
         public int findSecondMinimumValue(TreeNode root) { 
            if(root == null){ 
                return -1;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            int res = 2147483647;
            int flag = 0;
            while(queue.size() != 0){ 
                for(int i = 0;i < queue.size();i++){ 
                TreeNode node = queue.poll();
                if(node.val != root.val){ 
                    res = Math.min(res,node.val);
                }
                if(node.val == 2147483647){ 
                    flag = 1;
                }
                
                if(node.left != null){ 
                    queue.add(node.left);
                }
                if(node.right != null){ 
                    queue.add(node.right);
                }    
            }
            }
            if(res == 2147483647 && flag == 0){ 
                return -1;
            }
            return res;
        }
    }