题目：https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

我的方法一：深度优先搜索（递归）

步骤

思路，先看看左边子树的节点树是多少，如果节点树等于k-1，那么当前的节点就是第k个；如果小于k-1，那么应该在右树里面；

1. 先求的左子树的节点个数，如果节点树等于k-1，那么当前的节点就是第k个，停止遍历；
2. 如果节点树小于k-1，那么应该在右树里面，但是注意，由于右子树不好知道前面当前节点和左子树的节点数量总和，所以需要转为k在右子树里第几个，所以应该是（k-左子树节点树-1【1表示当前节点】）;
3. 由于是递归，从左子树算起，所以实际中不会计算到左子树节点数大于k-1
   的情况就已经停止了，所以这个分支可以写也可以不写；

边界条件

1. 当节点为空时，停止
2. 当左子树的数量是k-1时，当前节点就是第k个，停止遍历

复杂度

时间复杂度：O(n)，最坏的情况就是遍历所有的节点，所以是O(n)
空间复杂度：O(n)，因为是递归调用，最坏情况是只有左子树，递归了所有点，所以栈深度也是n

代码

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int value = -1;
        dfs(root, k, value);
        return value;
    }

private:
    //return count include node 
    int dfs(TreeNode* node, int k, int &value){
        if(!node){
            return 0;
        }

        int left_count = dfs(node->left, k, value);
        if(value >= 0){
            return left_count;      
        }

        if(left_count == k - 1){
            value = node->val;
            return left_count+1;
        }else if(left_count > k - 1){
            return left_count+1;
        }

        int right_count = dfs(node->right, k - left_count - 1, value);
        return left_count + right_count + 1;
    }
};

我的方法二：深度优先搜索（迭代）

是在方法一基础修改的，直接看代码

/**
 * 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:
    int kthSmallest(TreeNode* root, int k) {
        if(!root){
            return k;
        }

        int value = -1;
        int left_count = 0;

        stack<pair<bool, TreeNode*>>s;//模拟参数栈，由于不是尾递归，所以一个参数需要二次压入参数栈，bool代表是否二次压入了参数栈，初始值是false
        s.emplace(false, root);//模拟首次调用dfs

        while(!s.empty()){//模拟dfs是否调用到了底
            pair<bool, TreeNode*> cur_param = s.top();
            s.pop();

            if(!cur_param.second){
                continue;//模拟dfs函数判断当前节点是否为空
            }

            if(cur_param.first){
                left_count++;
                if(left_count == k){
                    value = cur_param.second->val;
                    break;
                }
                //模拟处理右节点
                s.emplace(false, cur_param.second->right);
            }else{
                //模拟首次调用到一个节点时，先处理左节点，然后再处理当前节点，因为栈先进后出，所以两个反过来
                s.emplace(true, cur_param.second);
                s.emplace(false, cur_param.second->left);
            }
        }

        return value;
    }
};