题目

给定一个所有节点为非负值的二叉搜索树，求树中任意两节点的差的绝对值的最小值。

解题思路

二叉搜索树的特点是：左节点小于根节点值，右节点大于根节点的值。所以最小绝对差存在于某个根节点和它的左节点或右节点之间。可以先用中序遍历将节点值存在一个数组中，比较数组中相邻两数差的最小值。

代码如下：

TreeNode.h

#pragma once
#include<iostream>
#include<vector>
using namespace std;
struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {};
};

Tree.h

#pragma once
#include"TreeNode.h"
class Tree
{
public:
	int getMinimumDifference();
	void Insert(int m);
	void midorder();
private:
	void search_insert(TreeNode*& p, int m);
	void recursive_midorder(TreeNode* p);
	vector<int> mid;
	TreeNode* root = NULL;
};

Tree.cpp

#include "Tree.h"
void Tree::search_insert(TreeNode*& sub_root, int m)
{
	if (sub_root == NULL)
		sub_root = new TreeNode(m);
	else if (m < sub_root->val)
		search_insert(sub_root->left, m);
	else
		search_insert(sub_root->right, m);
}
void Tree::Insert(int m)
{
	search_insert(root, m);
}
void Tree::midorder()
{
	recursive_midorder(root);
}
void Tree::recursive_midorder(TreeNode* p)
{
	if (p != NULL)
	{
		recursive_midorder(p->left);
		mid.push_back(p->val);
		recursive_midorder(p->right);
	}
}
int Tree::getMinimumDifference()
{
	if (!root) 
		return 0;
	int min = INT_MAX;
	for (int i = 0; i < mid.size() - 1; i++) 
	{
		if (mid[i + 1] - mid[i] < min) 
			min = mid[i + 1] - mid[i];
	}
	return min;
}

main.cpp

#include"Tree.h"
int main()
{
	Tree t;
	int num;
	while (cin >> num)
	{
		t.Insert(num);
		if (cin.get() == '\n')
			break;
	}
	t.midorder();
	int m=t.getMinimumDifference();
	cout << m;
	return 0;
}