783. 二叉搜索树节点最小距离

￡神魔★判官ぃ 2023-03-01 10:19 122阅读 0赞

定一个二叉搜索树的根节点 root，返回树中任意两节点的差的最小值。

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

中序遍历：

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
        
    public:
        int minDiffInBST(TreeNode* root) {
        
            TreeNode *pre = NULL;
            int res = INT_MAX;
            midorder(root, res, pre);
            return res;
        }
    
        void midorder(TreeNode* root, int& res, TreeNode *&pre){
        
            if(!root) return;
            midorder(root->left, res, pre);
            if(pre) res = min(res, root->val - pre->val);
            pre = root;
            midorder(root->right, res, pre); 
        }
    };

后序遍历：

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
        
    public:
        int minDiffInBST(TreeNode* root) {
        
            int temp = INT_MAX;
            if(!root) return temp;
            if(root->left){
        
                TreeNode *tmp = root->left;
                while(tmp->right) tmp = tmp->right;
                temp = min(temp, root->val - tmp->val);
            }
            if(root->right){
        
                TreeNode *tmp = root->right;
                while(tmp->left) tmp = tmp->left;
                temp = min(temp, tmp->val - root->val);
            }
            return min(temp, min(minDiffInBST(root->left), minDiffInBST(root->right)));
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1amlhbjIzMw_size_16_color_FFFFFF_t_70]: /images/20230209/b1499801c180407b87c37b7de2aa0044.png
[leetcode]: https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/