二叉搜索树中第K小的元素Kth Smallest Element in a BST解方法一递归中序遍历一次中序遍历即可/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; *///全局变量inti0;intval0;voidldr(structTreeNode*root,intk){if(rootNULL){return;}ldr(root-left,k);if(--i0){valroot-val;}ldr(root-right,k);}intkthSmallest(structTreeNode*root,intk){ik;ldr(root,k);returnval;}结果提前终止版/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */inti0;intval0;voidldr(structTreeNode*root,intk){if(rootNULL){return;}ldr(root-left,k);if(--i0){valroot-val;}elseif(i0){return;}ldr(root-right,k);}intkthSmallest(structTreeNode*root,intk){ik;ldr(root,k);returnval;}结果方法二非递归中序遍历偷点懒用的C/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */classSolution{public:intkthSmallest(TreeNode*root,intk){stackTreeNode*s;vectorintret;TreeNode*temproot;while(!s.empty()||temp!NULL){while(temp!NULL){s.push(temp);temptemp-left;}temps.top();s.pop();ret.push_back(temp-val);temptemp-right;}returnret[k-1];}};结果方法三通过结点个数判断/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; *///计数节点个数intcount(structTreeNode*root){if(rootNULL){return0;}returncount(root-left)count(root-right)1;}intkthSmallest(structTreeNode*root,intk){intncount(root-left);if(n1k){//所查点为根节点returnroot-val;}elseif(nk){//所查点在左子树上returnkthSmallest(root-left,k);}else{//所查点在右子树上returnkthSmallest(root-right,k-n-1);}return0;}结果方法四Moris遍历有关该算法讲解在这/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */intkthSmallest(structTreeNode*root,intk){intindex0;structTreeNode*currentroot;//int ret 0;while(current!NULL){if(current-leftNULL){index;if(indexk){returncurrent-val;}currentcurrent-right;}else{structTreeNode*tempcurrent-left;while(temp-right!NULLtemp-right!current){temptemp-right;}if(temp-rightNULL){temp-rightcurrent;currentcurrent-left;}if(temp-rightcurrent){index;if(indexk){returncurrent-val;}temp-rightNULL;currentcurrent-right;}}}return0;}结果
