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

class Solution {
public:

    stack<TreeNode*> mystack;
    //思路分析：这道题要求给出第k小（第k大其实也是一个道理）的数，而且是在二叉搜索数上的。由于二叉搜索数的左小右大的特性，这道题可以转化为“先遍历二叉搜索树，将树转化为一个有序的数组，最后再找到第k个即可。”
    //写递归的时候，边界条件：自身为空。顺序：右孩子比自己大，先入栈，自己接着入栈，最后左孩子入栈。自己入栈时直接写就行，左右孩子则递归调用。
    void solve(TreeNode* proot)
    {
        if(proot==nullptr)
            return;
        solve(proot->right);
        mystack.push(proot);
        solve(proot->left);
    }

    int KthNode(TreeNode* proot, int k) {
        // write code here       
        solve(proot);
        if(proot==nullptr || k>mystack.size() || k<=0)
            return -1;
        int result=0;
        TreeNode* temp=nullptr;
        while (k>0) {
            result=mystack.top()->val;
            mystack.pop();
            k--;
        }
        return result;
    }
};