LeetCode演算法題-Second Minimum Node In a Binary Tree（Java實現）
摘要：
這是悅樂書的第285
次更新，第302
篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第153題（順位題號是671）。給定非空的特殊二叉樹，其由具有非負值的節點組成，其中該樹中的每個節點具有恰好兩個或零個子節...
這是悅樂書的第285 次更新，第302 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第153題（順位題號是671）。給定非空的特殊二叉樹，其由具有非負值的節點組成，其中該樹中的每個節點具有恰好兩個或零個子節點。 如果節點具有兩個子節點，則該節點的值是其兩個子節點中的較小值。給定這樣的二叉樹，您需要輸出由整個樹中所有節點的值組成的集合中的第二個最小值。如果不存在這樣的第二個最小值，則輸出-1。例如：
2 / \ 25 / \ 57
輸出：5
2 / \ 22
輸出：-1
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
使用HashSet和遞迴。將每一個節點值新增進set，然後遍歷set，找出其中第二小的值，最後輸出即可。
/**
* 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) {
Set<Integer> set = new HashSet<Integer>();
helper(root, set);
int min = Integer.MAX_VALUE;
int second = Integer.MAX_VALUE;
for (int value : set) {
if (value < min) {
second = min;
min = value;
} else if (value < second) {
second = value;
}
}
if (min == second) {
return -1;
}
return second == Integer.MAX_VALUE ? -1 : second;
}
public void helper(TreeNode node, Set<Integer> set){
if (node == null) {
return ;
}
set.add(node.val);
helper(node.left, set);
helper(node.right, set);
}
}
03 第二種解法
我們也可以不使用HashSet。依舊使用遞迴，但是將最小值，第二最小值作為了全域性變數，最小值只申明，在方法內部初始化為根節點的節點值。在遞迴方法裡，如果當前節點值大於最小值且小於第二小值，那麼就更新第二小的值；如果當前節點值等於最小值，就繼續遍歷其左子節點和右子節點。
/**
* Definition for a binary tree node.
* public class TreeNode {
*int val;
*TreeNode left;
*TreeNode right;
*TreeNode(int x) { val = x; }
* }
*/
class Solution {
int min ;
int second = Integer.MAX_VALUE;
public int findSecondMinimumValue(TreeNode root) {
min = root.val;
helper(root);
if (min == second) {
return -1;
}
return second == Integer.MAX_VALUE ? -1 : second;
}
public void helper(TreeNode node) {
if (node == null) {
return ;
}
if (node.val > min && node.val < second) {
second = node.val;
} else if (node.val == min) {
helper(node.left);
helper(node.right);
}
}
}
04 第三種解法
針對第一種解法，也可以使用迭代的方式。
/**
* 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) {
Set<Integer> set = new HashSet<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode temp = stack.pop();
set.add(temp.val);
if (temp.left != null) {
stack.push(temp.left);
}
if (temp.right != null) {
stack.push(temp.right);
}
}
int min = Integer.MAX_VALUE;
int second = Integer.MAX_VALUE;
for (int value : set) {
if (value < min) {
second = min;
min = value;
} else if (value < second) {
second = value;
}
}
if (min == second) {
return -1;
}
return second == Integer.MAX_VALUE ? -1 : second;
}
}
05 第四種解法
針對第二種解法，也可以使用迭代的方式。
/**
* 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) {
int min = root.val;
int second = Integer.MAX_VALUE;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node.val > min && node.val < second) {
second = node.val;
} else if (node.val == min) {
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
}
if (min == second) {
return -1;
}
return second == Integer.MAX_VALUE ? -1 : second;
}
}
06 小結
演算法專題目前已日更超過四個月 ，演算法題文章153 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！