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

喜欢ヅ旅行 2022-12-20 11:08 188阅读 0赞

# 题目来源 #

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

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]

# 题目解析 #

1.没有必要记录最小的值，因为最小的一定是根结点。  
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 {
        
    public int findSecondMinimumValue(TreeNode root) {
        
            if (root == null){
        
                return -1;
            }
    
            return helper(root, root.val);
        }
    
        private int helper(TreeNode root, int val){
        
            if (root == null){
        
                return -1 ;
            }
    
            if (root.val != val){
        
                return root.val;
            }
    
            int l = helper(root.left, val);
            int r = helper(root.right, val);
            if (l == -1){
        
                return r;
            }
            
            if (r == -1){
        
                return l;
            }
           
    
            return Math.min(l, r);
        }
    }

[671.]: https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/dcad59a9898a46af9fdf97afb2b3f408.png