[LeetCode] 671. Second Minimum Node In a Binary Tree

轉自LeetCode

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly twoor 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.

<Solution>

想法如下

• 一開始想歷遍 tree 加上 TreeSet，這樣可以濾掉重複的數字外，還可以順便排序。會過，但是效率不夠好

• 因為題目的規定，min 一定會是 root.val，配合 recursive 的方式去歷遍找答案

• 如果某個 node.val 比目前找到的答案大，也不用再檢查下去

• 如果某個 node.val 比 min 大且比目前的答案小，更新答案，然後也不用檢查下去，因為題目規定，如果有左右子樹，根的值一定是最小的了

code 如下

Java(參考解答)

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	private int ans = Integer.MAX_VALUE;
	private int min;
	public int findSecondMinimumValue(TreeNode root) {
	min = root == null ? -1 : root.val;
	dfs(root);
	return ans < Integer.MAX_VALUE ? ans : -1;
	}
	private void dfs(TreeNode root) {
	if(root == null) {
	return;
	}
	if(min < root.val && root.val < ans) {
	ans = root.val;
	}
	else if(min == root.val) {
	dfs(root.left);
	dfs(root.right);
	}
	}
	}

view raw findSecondMinimumValueInBinaryTree.java hosted with ❤ by GitHub

kotlin

	/**
	* Example:
	* var ti = TreeNode(5)
	* var v = ti.`val`
	* Definition for a binary tree node.
	* class TreeNode(var `val`: Int) {
	* var left: TreeNode? = null
	* var right: TreeNode? = null
	* }
	*/
	class Solution {
	private var ans = Long.MAX_VALUE
	private var min = -1
	fun findSecondMinimumValue(root: TreeNode?): Int {
	min = root?.let { it.`val` } ?: -1
	dfs(root)
	return if(ans < Long.MAX_VALUE) ans.toInt() else -1
	}
	private fun dfs(node: TreeNode?) {
	if(node == null) {
	return
	}
	if(min < node.`val` && node.`val` < ans) {
	ans = node.`val`.toLong()
	return
	}
	dfs(node.left)
	dfs(node.right)
	}
	}

view raw second_minimum_node_in_a_binary_tree.kt hosted with ❤ by GitHub