一定要早日上岸鸭 · July 27, 2021 0

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

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

此题有三种情况:

可以定义两个小值 d1, d2

  1. 若树上的值 X < d1 < d2 --> d1 = X d2 = d1;
  2. 若树上的值 d1 < X < d2 --> d2 = X;
  3. 若树上的值 d1 < d2 < X --> 不变// DFS:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ // 此题有三种情况: // 可以定义两个小值 d1, d2 // 若树上的值 X < d1 < d2 --> d1 = X d2 = d1; // 若树上的值 d1 < X < d2 --> d2 = x; // 若树上的值 d1 < d2 < X --> 不变 // DFS: class Solution { public static long d1; public static long d2; public void DFS(TreeNode TN){ if(TN==null) return; int X = TN.val; if(X<d1){ d2 = d1; d1 = X; } else if(d1<X && X<d2){ d2 = X; } DFS(TN.left); DFS(TN.right); } public int findSecondMinimumValue(TreeNode root) { d1 = Long.MAX_VALUE; d2 = Long.MAX_VALUE; DFS(root); return d2 == Long.MAX_VALUE ? -1:(int)d2; } }