【剑指offer】二叉搜索树的第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)
    {
        /*
          中序遍历递归写法
          void InOrder(TreeNode* Root, TreeNode* &res){
              if(!res) return;
              if(Root){
                  InOrder(Root->left);
                  count--;
                  if(count == 0) res = Root;
                  InOrder(Root->right);
              }
          }
        */
        //中序遍历非递归写法
        if(!pRoot || k < 1) 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;
    }


};