题解 | #二叉搜索树的第k个结点#

方法1：递归
我们要知道二叉搜索树的性质，对于每个节点，其左子树中所有点的点权小于(等于)它，其右子树的所有点的点权大于它。
我们可以根据这个性质来递归查找第k小的值
有一个巧妙的处理方法，我们从根开始一直往左子树深搜，那么搜索结束的时候所在的节点一定是最小的。然后我们回溯，这样就能按照从小到大的顺序回去，一边回去一边让k - 1，当k为1的时候，当前节点就是答案了。
我们假设有这么一个二叉搜索树

然后我们要找到它的第4小的值，于是我们可以这样找
我们从根节点开始，一直递归到底部，当前k为4

当前值不是1，所以要减去1然后回溯

当前值不是1，所以要减去1然后回溯

当前值不是1，发现有右子树，于是我们减去1之后到右节点继续数

注意到当前已经变成1，所以当前值就是答案。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    TreeNode* res;//记录答案用
    void dfs(TreeNode* tmp, int &m) {
        //由于m是要减少的，所以要引用
        if (tmp == NULL || m < 1) return ;//这里是空节点或者m < 1的非法情况，直接返回
        dfs(tmp->left, m);//否则先往左子树深搜，找出最小值
        if (m == 1) res = tmp;//若当前的m为1，说明是答案，记录答案
        m --;//否则就要回溯
        dfs(tmp->right, m);//回去的时候，如果有右子树，那就走右子树
    }
    TreeNode* KthNode(TreeNode* pRoot, int k) {
        res = NULL;
        dfs(pRoot, k);
        return res;
    }

};

方法2：非递归写法
方法和上面类似，我们利用栈来实现非递归写法
因为递归的原理就是栈，这里其实就是用栈来模拟了递归

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k) {
        if (pRoot == NULL) return NULL;//特判空树的情况
        stack<TreeNode* > sta;
        TreeNode* res = pRoot;//存答案，初始为根节点
        while (!sta.empty() || res != NULL) {//当栈为空并且当前节点为空节点的时候结束迭代
            while (res != NULL) {//我们先把当前节点往左节点搜到底
                sta.push(res);
                res = res->left;
            }
            res = sta.top();//然后开始回溯
            sta.pop();
            if (k == 1) return res;//如果为1，说明就是答案，直接返回
            k --;
            res = res->right;//否则我们继续往右子树数
        }
        return NULL;
    }
};