Problem
Solution
Initial thoughts
Python implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
|
class : def findSecondMinimumValue(self, root): """ :type root: TreeNode :rtype: int """ self._min_val = float("inf") self._sec_min = float("inf") def dfs(node): if node is None: return node if node.val < self._min_val: self._min_val, self._sec_min = node.val, self._min_val if self._min_val < node.val < self._sec_min: self._sec_min = node.val dfs(node.left) dfs(node.right) dfs(root) return self._sec_min if self._sec_min < float("inf") else -1
|
Java implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
|
* Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class { private int minVal = Integer.MAX_VALUE; private int secVal = Integer.MAX_VALUE; private void dfs(TreeNode node){ if(node==null){ return ; } if(node.val < minVal){ secVal = minVal; minVal = node.val; } if(minVal < node.val && node.val < secVal){ secVal = node.val; } dfs(node.left); dfs(node.right); } public int findSecondMinimumValue(TreeNode root) { dfs(root); return secVal < Integer.MAX_VALUE ? secVal : -1; } }
|
Time complexity
O(n)
Space complexity
O(n)
Links
671. Second Minimum Node In a Binary Tree
(中文版) 算法笔记: 力扣#671 二叉树中第二小的节点
近期评论