二叉树——二叉搜索树的最小绝对差

二叉搜索树的最小绝对差

链接
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

输入：root = [4,2,6,1,3]
输出：1
示例 2：

输入：root = [1,0,48,null,null,12,49]
输出：1

提示：

树中节点的数目范围是 [2, 104]
0 <= Node.val <= 105

递归法

方法一

用中序遍历把二叉搜索树的值存在vector< int >中，成单调递增，计算差值就可以了

方法二

在递归中直接计算

• 返回值——int（差值）
  参数——节点

void traversal(TreeNode* root)

• 终止条件
  节点为空，差值为1（最小差值），看提示节点数最小2个不需要考虑节点为0和1的情况

        if(root==NULL || res==1) return;

• 单次递归
  虽然题目为任意两个节点，但搜索二叉树成中序排列，差值最小出现在相邻处
  定义全局变量

    int res=INT_MAX;TreeNode* pre=NULL;

中序递归

        if(root->left)traversal(root->left);//左if(root!=NULL&& pre!=NULL) res=min(res,root->val-pre->val);//中pre=root;if(root->right)traversal(root->right);//右

中的操作有两步

1. 计算差值，取最小值
2. 记录上一个节点

代码

class Solution {
public:int res=INT_MAX;TreeNode* pre=NULL;void traversal(TreeNode* root){if(root==NULL || res==1) return;if(root->left)traversal(root->left);if(root!=NULL&& pre!=NULL) res=min(res,root->val-pre->val);pre=root;if(root->right)traversal(root->right);}int getMinimumDifference(TreeNode* root) {traversal(root);return res;}
};