温州市网站建设_网站建设公司_产品经理_seo优化

Problem: 783. Minimum Distance Between BST Nodes 二叉搜索树节点最小距离

解题过程

耗时100%，树bst的中序遍历【左根右】就是所有node值排序以后的结果，所以最小值一定在相邻两个数字差之间

Code

/** * Definition for a binary tree node. * 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: vector<int> tr; void midTra(TreeNode* root) { if(root==nullptr) return; midTra(root->left); tr.push_back(root->val); midTra(root->right); } int minDiffInBST(TreeNode* root) { int mi = INT_MAX; midTra(root); for(int i = 1; i < tr.size(); i++) { mi = min(mi, tr[i] - tr[i-1]); } return mi; } };