【DFS&BFS】671. 二叉树中第二小的节点（简单）
让我们先来看看这道题目的描述
方法一：无脑遍历，找到次小的值（前序遍历递归版本）
/*** 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;* }* }*/class Solution{TreeSet<Integer> set = new TreeSet();public int findSecondMinimumValue(TreeNode root) {dfs(root);Queue<Integer> queue = new LinkedList<>();for(int s : set){queue.offer(s);}if(queue.peek() != null) queue.poll();return queue.peek() == null ? -1 : queue.peek();}private void dfs(TreeNode root){if(root == null){return;}set.add(root.val);dfs(root.left);dfs(root.right);}}
方法一：无脑遍历，找到次小的值（BFS版本）
/*** 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;* }* }*/class Solution{TreeSet<Integer> set = new TreeSet();public int findSecondMinimumValue(TreeNode root) {bfs(root);Queue<Integer> queue = new LinkedList<>();for(int s : set){queue.offer(s);}if(queue.peek() != null) queue.poll();return queue.peek() == null ? -1 : queue.peek();}private void bfs(TreeNode root){if(root != null) set.add(root.val);Queue<TreeNode> q = new LinkedList<>();q.offer(root);while(!q.isEmpty()){int size = q.size();for(int i = 0; i < size; ++i){TreeNode cur = q.poll();set.add(cur.val);if(cur.left != null) q.offer(cur.left);if(cur.right != null) q.offer(cur.right);}}}}
显然这两种方法都没有用到题目给出的条件，结合一幕，我们可以分析出根节点的值一定是最小的值，我们可以用第一个大于根节点的值充当次小值，不断比较，如果遇到了比当前次小值更小的值，则将新的值设置为次小值
/*** 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;* }* }*/class Solution{int first;int second;public int findSecondMinimumValue(TreeNode root) {if(root == null) return second;first = root.val;second = -1;dfs(root);return second;}private void dfs(TreeNode root){if(root == null){return;}if (second != -1 && root.val >= second) {return;}if(root.val > first){second = root.val;}dfs(root.left);dfs(root.right);}}