This is the seventh day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Hello, everyone, today is the 7th day I participated in the August more text, today brings you about the binary tree related algorithm problem is to find the second smallest node in the binary tree, the text is as follows:

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:

Input: root = [2,2,5, NULL, NULL,5,7] Output: 5 Explanation: The smallest value is 2, and the second smallest value is 5.Copy the code

Example 2:

Input: root = [2,2,2] Output: -1 Explanation: The minimum value is 2, 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

Thought analysis

For any node x in a binary tree, the value of x is not greater than the value of all nodes in the subtree whose root is x. Therefore, the root of the binary tree is the minimum value of all nodes.

Therefore, we can traverse the whole binary tree to find the smallest value larger than the root node, which is the second smallest value among all nodes.

We can use a depth-first search method to traverse the binary tree.

Since root.val is the smallest in the tree, the val traversed to any node is strictly larger than root.val.

When such nodes are found, we record the minimum. Since the val of any node is the minimum value in the left and right subtrees, you can return it directly without continuing to recursively search the subtrees.

Code implementation

/** * 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 ans = Integer.MAX_VALUE;
    boolean find = false;
    public int findSecondMinimumValue(TreeNode root) {
        if (root.left == null) return -1;
        // The first minimum value must be root.val
        int val = root.val;

        helper(root, val);
        return! find ? -1 : ans;
    }

    public void helper(TreeNode r, int val) {
        // Because each node can only have 0 or 2 children
        // When null, return
        if (r == null)  return ;

        / / because root. Val is the least of the tree, so the traversal to any one node val is not equal to the root. Val,
        // Both are greater than root.val. When such nodes are found, we record the minimum. Because any node
        // val is the minimum value in the left and right subtrees, so it can be returned directly without continuing to recursively search the subtrees.
        if(r.val ! = val) { ans = Math.min(r.val, ans); find =true;
            return; } helper(r.left, val); helper(r.right, val); }}Copy the code

The last

Complexity analysis

  • Time complexity: O(n), where n is the number of nodes in the binary tree. At most, we need to walk the whole tree once.

  • Space complexity: O(n). We use a depth-first search method for traversal, and the stack space required is O(n).