leetcode.783. 二叉搜索树节点最小距离(minimum-distance-between-bst-nodes)

怼烎@ 2022-11-18 10:53 107阅读 0赞

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

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

\*\*注意：\*\*本题与 530：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/ 相同

**示例 1：**

![f2233d1bcd1930ff4b184a13723597b9.png][]

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

**示例 2：**

![488f03721e85771e6945d0f02ae7048b.png][]

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

**提示：**

*  树中节点数目在范围 `[2, 100]` 内
 *  0 <= `Node.val` <=  1 0 5 10^\{5\} 105

# 思路与代码 #

如果一个数组是升序的，求它们两任意两个元素的最小值，答案一定为相邻两个元素之差的最小值 .看下图，  
数组是升序的，11减去2得到的差为9，肯定没有7送去2得到的差5小。

因为二叉搜索树中序遍历得到的值序列是递增有序的，所以可以用中序遍历来解决[本题][Link 1]。

#include <iostream>
    #include <vector>
    
    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 { 
    private:
    	void dfs(TreeNode* root, int& pre, int& ans) { 
    		if (root == nullptr) { 
    			return;
    		}
    		dfs(root->left, pre, ans);
    		if (pre == -1) { 
    			pre = root->val;
    		}
    		else { 
    			ans = min(ans, root->val - pre);
    			pre = root->val;
    		}
    		dfs(root->right, pre, ans);
    	}
    public:
    	int minDiffInBST(TreeNode* root) { 
    		int ans = INT_MAX, pre = -1;
    		dfs(root, pre, ans);
    		return ans;
    	}
    };
    
    int main()
    { 
    	TreeNode t4(4);
    	TreeNode t2(2);
    	TreeNode t6(6);
    	TreeNode t1(1);
    	TreeNode t3(3);
    
    	t4.left = &t2;
    	t4.right = &t6;
    	t2.left = &t1;
    	t2.right = &t3;
    
    	Solution s;
    	cout << s.minDiffInBST(&t4) << endl;
    
    }

二叉树的中序遍历有多种方式，包括递归、栈、Morris 遍历等，读者可选择自己最擅长的来实现。下文代码提供最普遍的递归方法来实现，其他遍历方法的介绍可以详细看「[94. 二叉树的中序遍历的官方题解」，这里不再赘述][94.]。

[783.]: https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/
[f2233d1bcd1930ff4b184a13723597b9.png]: /images/20221022/51ff088742914cfe90d86070a60878c5.png
[488f03721e85771e6945d0f02ae7048b.png]: /images/20221022/8951f92061cd4f84978fb9e0470aac1e.png
[Link 1]: https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/solution/er-cha-sou-suo-shu-jie-dian-zui-xiao-ju-8u87w/
[94.]: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/