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

class Solution {
public:
    int KthNode(TreeNode* proot, int k) {
        if(!proot) return -1;
        stack<TreeNode*>sta;
        sta.push(proot);
        TreeNode *leftNode = proot;
        int cot = 0;
        while(!sta.empty()){
            while(leftNode->left != nullptr){
                sta.push(leftNode->left);
                leftNode = leftNode->left;
            }
            cot ++;
            TreeNode *temp_node = sta.top();
            sta.pop();
            if(cot == k ) return temp_node->val;
            if(temp_node->right){
                sta.push(temp_node->right);
                leftNode = temp_node->right;
            }
             
        }
        return -1;
    }
};

模拟一下递归，原理算是BFS递归版

1. 先把所有的左孩子加入到栈中(和递归差不多，递归也是先一条路走到底)，此时栈顶元素为树中左孩子最底下那一个(位置为底部的左边)
2. 弹出栈顶，加入弹出栈顶的兄弟节点,此时需要判断右节点是否存在，对弹出栈顶进行计数

插个眼，C++ 版，不得不说，牛客的markdown好像有点小问题