二叉搜索树的第k个结点

---

题目描述

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

解题思路

由于二叉搜索树的特殊性质，左树值<根结点<右树值。故可以通过中序遍历的方法，输出二叉树结点，然后输出第 k个结点值即可。

代码

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 || k <= 0)
            return NULL;
        KthNodeCore (pRoot);
        if (k > result.size())
            return NULL;
        return result[k - 1];
    }
private:
    vector<TreeNode*> result;
    // 中序遍历, 递归遍历
    void KthNodeCore (TreeNode* pRoot)
    {
        if (!pRoot)
            return;
        KthNodeCore (pRoot->left);
        result.push_back(pRoot);
        KthNodeCore (pRoot->right);
    }
};

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 || k <= 0)
            return NULL;
        stack<TreeNode*> s;
        TreeNode* node = pRoot;
        int count = 0; // 输出结点的个数
        while (node != NULL || !s.empty())
        {
            if (node != NULL)
            {
                s.push(node);
                node = node->left;
            }
            else
            {
                node = s.top();
                s.pop(); // 输出一个结点
                count++;
                if (count == k)
                    return node;
                node = node->right;
            }
        }
        return NULL;
    }
};

参考博文链接：https://cuijiahua.com/blog/2018/01/basis_61.html

https://www.nowcoder.com/questionTerminal/ef068f602dde4d28aab2b210e859150a?f=discussion