二叉搜索树第K个结点

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

我的几万个递归的代码：

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: int kth(TreeNode *pRoot){ return num(pRoot->left)+1; } int num(TreeNode *pRoot){ if(!pRoot) return 0; return num(pRoot->left) + num(pRoot->right)+1; } TreeNode* KthNode(TreeNode* pRoot, int k) { if(!pRoot || k <= 0) return NULL; int temp = kth(pRoot); if(temp == k) return pRoot; if(temp > k) return KthNode(pRoot->left, k); if(temp < k) return KthNode(pRoot->right, k-temp); } };

题意中序遍历： 递归：

class Solution { public: int count = 0; //计数器 TreeNode* KthNode(TreeNode* pRoot, int k) { if(!pRoot) return NULL; TreeNode *lnode = KthNode(pRoot->left, k); if(lnode) return lnode; count++; if(count == k) return pRoot; TreeNode *rnode = KthNode(pRoot->right, k); if(rnode) return rnode; } };

中序遍历非递归：

class Solution { public: TreeNode* KthNode(TreeNode* pRoot, int k) { if(!pRoot) return NULL; stack<TreeNode*> s; TreeNode *cur = pRoot; int count = 0; while(!s.empty() || cur) { if(cur) { s.push(cur); cur = cur->left; }else { cur = s.top(); s.pop(); count++; if(count == k) return cur; cur = cur->right; } } return NULL; } };