Created
April 12, 2021 16:57
-
-
Save lishunan246/e584e93eb78f00b19ad3a887cea62d51 to your computer and use it in GitHub Desktop.
783. 二叉搜索树节点最小距离
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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) {} | |
* }; | |
*/ | |
void add(TreeNode* p, std::stack<TreeNode*>* s) { | |
while (p != nullptr) { | |
s->push(p); | |
p = p->left; | |
} | |
} | |
class Solution { | |
public: | |
int minDiffInBST(TreeNode* root) { | |
int res = 9999999; | |
std::stack<TreeNode*> stack; | |
add(root, &stack); | |
int pre = -1; | |
while (!stack.empty()) { | |
auto* n = stack.top(); | |
auto cur = n->val; | |
if (pre != -1) { | |
res = std::min(res, cur - pre); | |
} | |
pre = cur; | |
stack.pop(); | |
add(n->right, &stack); | |
} | |
return res; | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment