LeetCode783. 二叉搜索树节点最小距离【中序遍历】

我不是女神ヾ 2022-11-18 13:52 166阅读 0赞

难度：简单  
题目描述：  
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70 1]

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
    class Solution { 
    public:
        void dfs(TreeNode* r,int &pre,int &ans){ 
            if(r==nullptr){ 
                return;
            }
            dfs(r->left,pre,ans);
            if(pre==-1){ 
                pre=r->val;
            }else{ 
                ans=min(ans,r->val-pre);
                if(ans==1){ 
                    return;
                }
                pre=r->val;
            }
            dfs(r->right,pre,ans);
        }
        int minDiffInBST(TreeNode* root) { 
            int ans=INT_MAX,pre=-1;
            dfs(root,pre,ans);
            return ans;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]: /images/20221022/bbfcae1e35bd44abb8c337a5c2faf91c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70 1]: /images/20221022/a3de28374c274ea59c0d518014e9ae41.png