二叉搜索树的第k个节点（C++）

给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。

返回第k小的节点值即可不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1保证n个节点的值不一样

数据范围：

进阶：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

如输入{5,3,7,2,4,6,8},3时，二叉树{5,3,7,2,4,6,8}如下图所示：

该二叉树所有节点按结点值升序排列后可得[2,3,4,5,6,7,8]，所以第3个结点的结点值为4，故返回对应结点值为4的结点即可。

输入：
{5,3,7,2,4,6,8},3
返回值：
4

输入：
{},1
返回值：
-1

备注：当树为空的时候。

  通过二叉树的中序遍历将节点进行排序，存放至线性结构（数组）中即可。

class Solution {
  public:
    
    vector arr;
    //通过递归来对二叉树进行中序遍历
    void Inorder(TreeNode* pHead) {
         if(pHead)
         {
             Inorder(pHead->left);
             arr.push_back(pHead->val);
             Inorder(pHead->right);
         }
    }
    int KthNode(TreeNode* proot, int k) {
        if (nullptr == proot ||
                (proot->left == nullptr && proot->right == nullptr && k != 1) ||
                k == 0)return -1;
        Inorder(proot);
        if (arr.size() < k)return -1;
        return arr[k - 1];
    }
};

class Solution {
  public:
    
    vector arr;
    //通过栈结构实现对二叉树的中序遍历
    void Inorder(TreeNode* pHead) {
        stack stack;
        TreeNode* tempNode, *pStart = pHead;
        while (pStart || !stack.empty()) {
            if (pStart) {
                stack.push(pStart);
                pStart = pStart->left;
            } else {
                tempNode = stack.top();
                arr.push_back(tempNode->val);
                stack.pop();
                pStart = tempNode->right;
            }
        }
    }
    int KthNode(TreeNode* proot, int k) {
        if (nullptr == proot ||
                (proot->left == nullptr && proot->right == nullptr && k != 1) ||
                k == 0)return -1;
        Inorder(proot);
        if (arr.size() < k)return -1;
        return arr[k - 1];
    }
};