671. Second Minimum Node In a Binary Tree - Easy
Given a non-empty special binary tree consisting of nodes with the non-negative value,where each node in this tree has exactly? 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. ? ref:?https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/discuss/107158/Java-divide-and-conquer-solution 如果节点为空,或者没有子节点,返回-1 如果子节点的值和当前节点一样,递归求next candidate;如果不同,子节点的值当作candidate 如果左右节点的值都不是 -1,返回其中较小的节点值,否则返回其中不等于-1的节点值 time: O(n),space: O(height) /** * 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; } if(root.left == null && root.right == null) { return -1; } int left = root.left.val; int right = root.right.val; if(root.left.val == root.val) { left = findSecondMinimumValue(root.left); } if(root.right.val == root.val) { right = findSecondMinimumValue(root.right); } if(left != -1 && right != -1) { return Math.min(left,right); } else if(left != -1) { return left; } else { return right; } } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |