2021-07-27 LeetCode One question of the day

Link: leetcode-cn.com/problems/se…

Tags: binary tree, depth-first search

The title

Given a non-null special binary tree, each node is a positive number, and each node can only have two or zero children. If a node has two children, the value of that node is equal to the smaller of the two children.

More formally, root.val = min(root.left.val, root.right.val) always holds.

Given a binary tree like this, you need to print the second smallest value of all the nodes. If the second smallest value does not exist, the output is -1.

Example 1:

Enter: root = [2.2.5.null.null.5.7] output:5Explanation: The minimum value is2, the second smallest value is5 。
Copy the code

Example 2:

Enter: root = [2.2.2] Output: -1Explanation: The minimum value is2, but there is no second smallest value.Copy the code

Tip:

  • The number of nodes in the tree is in the range [1, 25]
  • 1 <= Node.val <= 231 – 1
  • Val == min(root.left.val, root.right.val) for each node in the tree

Analysis of the

Idea 1: It’s normal to take all the nodes and sort them.

The value of the root node is the smallest at one point, so we can record the first value smaller than the root node in the process of traversing, and then let other nodes compare with this value, and take the smaller value, which is the second smallest value.

coding

Idea 1:

/** * 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 {
    public int findSecondMinimumValue(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        dfs(sb, root);
        String[] str = sb.substring(0, sb.length() - 1).toString().split(",");
        int[] array = Arrays.stream(str).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(array);
        int len = array.length;
        int min = array[0];
        for (int i = 1; i < len; i++) {
            if (array[i] > min) {
                returnarray[i]; }}return - 1;
    }

    private void dfs(StringBuilder sb, TreeNode node) {
        if (node.left == null && node.right == null) {
            sb.append(node.val).append(",");
            return; } dfs(sb, node.left); dfs(sb, node.right); }}Copy the code

The beat rate is pitifully low.

Idea 2:

/** * 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 min = -1;
    public int findSecondMinimumValue(TreeNode root) {
        dfs(root, root.val);
        return min;
    }

    private void dfs(TreeNode node, int val) {
        if (node == null) {
            return;
        }
        if(node.val ! = val) {// The first value greater than the root
            if (min == -1) {
                min = node.val;
            } else {
                min = Math.min(min, node.val);
            }
            // There is no need to search further, because the values below are all larger than the current node value
            return; } dfs(node.left, val); dfs(node.right, val); }}Copy the code