博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
783. 二叉搜索树节点最小距离
阅读量:779 次
发布时间:2019-03-25

本文共 1176 字,大约阅读时间需要 3 分钟。

在这里插入图片描述

两种方法,递归和迭代,总的来说就是不难,bst任意两个点的最小差,还不就是中序遍历两两相减吗?
为了防止数据太恶心,我们维护的是pre结点,不是int的pre,递归就是第一次不比较,但是要更新pre为root。不管有没有更新res,pre都要在比较后更新。
迭代也是一样第一次不比较

class Solution {
public: // void inOrderTrave(TreeNode* root){
// if(root == nullptr) return; // inOrderTrave(root->left); // //第一次不比较,只更新pre // if(pre != nullptr){
// res = min(root->val-pre->val,res); // } // pre = root; // inOrderTrave(root->right); // } int minDiffInBST(TreeNode* root) {
//bst的最小差值肯定是中序遍历的两个连续的结点差 //维护一个全局的res和一个pre结点,当用当前结点-pre更新res,比完之后更新一个pre //inOrderTrave(root); //用stack来模拟中序 //中序左根右,一直往左 stack
sta; while(!sta.empty() || root != nullptr){
while(root != nullptr){
sta.push(root); root = root->left; } root = sta.top(); sta.pop(); if(pre != nullptr){
res = min(root->val-pre->val,res); } pre = root; root = root->right; } return res; }private: int res = INT_MAX; TreeNode* pre = nullptr;};

转载地址:http://rajuk.baihongyu.com/

你可能感兴趣的文章