文章目录

• LeetCode刷题笔记-数据结构-day17
• • 230. 二叉搜索树中第K小的元素
  • • 1.题目描述
    • 2.解题思路
    • 3.代码
  • 173. 二叉搜索树迭代器
  • • 1.题目描述
    • 2.解题思路
    • 3.代码

LeetCode刷题笔记-数据结构-day17

230. 二叉搜索树中第K小的元素

1.题目描述

原题链接：230. 二叉搜索树中第K小的元素

2.解题思路

算法：DFS

由题意可知这是一个二叉搜索树，我们所求的第K个小的元素等价于中序遍历到的第K个元素。

这里dfs方法返回bool值，相等于找到了答案直接返回，不用做多余的遍历，减少了时间复杂度。

3.代码

class Solution {
public:
    int sum=0,res;
    int kthSmallest(TreeNode* root, int k) {
        dfs(root,k);
        return res;
    }
    bool dfs(TreeNode* root,int k){
        if(!root) return false;
        if(dfs(root->left,k)) return true;
        sum++;
        if(sum==k){
            res=root->val;
            return true;
        }
        return dfs(root->right,k);
    }
};

173. 二叉搜索树迭代器

1.题目描述

原题链接：173. 二叉搜索树迭代器

2.解题思路

二叉搜索树本身中序遍历后的元素是从小到大排序，因此找下一个最小的数，即在中序遍历中找当前元素的下一个元素。

我们可以用栈模拟一个二叉搜索树迭代器，对应的三个方法实现：

1. BSTIterator(TreeNode* root)：初始化方法，将二叉搜索树的左边一条链压入栈，此时栈顶为最小元素
2. next()：取出栈顶元素，并移除栈顶元素，需要判断当前节点是否还有右子树，有的话，和方法BSTIterator(TreeNode* root)一样将右子树的左边一条链压入栈，同样保证了栈顶元素为最小元素
3. hasNext()：等价于判断当前栈是否还有元素

3.代码

class BSTIterator {
public:
    stack<TreeNode*> st;
    BSTIterator(TreeNode* root) {
        while(root){
            st.push(root);
            root=root->left;
        }
    }
    
    int next() {
        auto t=st.top();
        st.pop();
        int res=t->val;
        t=t->right;
        while(t){
            st.push(t);
            t=t->left;
        }
        return res;
    }
    
    bool hasNext() {
        return st.size();
    }
};