530、二叉搜索树的最小绝对差

1、题目描述

. - 力扣（LeetCode）

要求：给定一颗二叉树，返回树中任意不同节点值之间的最小差值。 

2、分析

(1)既然是二叉搜索树肯定想到中序遍历序列。"任意节点最小差值"其实就是中序序列相邻俩节点的最小差值。

(2)和98题一样。中序遍历，在遍历的时候记录最小差值即可。

class Solution {
public:
    int min_diff = INT_MAX;
    TreeNode* pre = NULL;
    int getMinimumDifference(TreeNode* root) {
        inorderTraversal(root);
        return min_diff;
    }
    void inorderTraversal(TreeNode* root){
        if(root == NULL) return;
        //左
        inorderTraversal(root->left); 
        //中
        if(pre != NULL){
            min_diff = min(min_diff, root->val - pre->val);
        }
        pre = root; //更新pre节点
        //右
        inorderTraversal(root->right);
    }
};

 

3、实现代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <math.h>

using namespace std;


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:
    int min_diff = INT_MAX;
    TreeNode* pre = NULL;
    int getMinimumDifference(TreeNode* root) {
        inorderTraversal(root);
        return min_diff;
    }
    void inorderTraversal(TreeNode* root){
        if(root == NULL) return;
        //左
        inorderTraversal(root->left); 
        //中
        if(pre != NULL){
            min_diff = min(min_diff, root->val - pre->val);
        }
        pre = root; //更新pre节点
        //右
        inorderTraversal(root->right);
    }
};


int main()
{
    Solution s1;
    TreeNode node4(1);
    TreeNode node5(3);
    TreeNode node3(5);
    TreeNode* pnode2 = new TreeNode(2, &node4, &node5);
    TreeNode root(4, pnode2, &node3);

    bool valid = s1.getMinimumDifference(&root);
    cout << "valid:" << valid << endl;
   
}

 

原文地址：https://blog.csdn.net/mijichui2153/article/details/142728678

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！