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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <iostream>
class Solution {
public:
    int KthNode(TreeNode* proot, int k) {
        if(proot == nullptr){
            return -1;
        }
        
        int count = 0;
        stack<TreeNode*> stk;
        TreeNode* root = proot;  //用root指针来跟踪当前的节点，如果直接跟踪栈的顶点，那么会重复进行左侧深入

        while(root || !stk.empty()){  //root可能没有没有右节点，直接上一层取stk；

            while(root){  //向左边深入
                stk.push(root);
                root = root->left;
            }

            root = stk.top();stk.pop();  //检测

            count++;
            if(count == k)return root->val;

            root = root->right;
        }
            
        return -1;
    }
};