1 /*************************************************************************
 2     > File Name: jz63.cpp
 3     > Author: wangshujing 
 4     > Mail: wangshujing@163.com
 5     > Created Time: 2017年06月08日 星期四 11时01分05秒
 6  ************************************************************************/
 7 // 剑指offer 第 63 题：二叉搜索树的第k个节点
 8 #include<iostream>
 9 using namespace std;
10 
11 
12 /*
13 struct TreeNode {
14     int val;
15     struct TreeNode *left;
16     struct TreeNode *right;
17     TreeNode(int x) :
18             val(x), left(NULL), right(NULL) {
19     }
20 };
21 */
22 
23 
24 class Solution{
25 public:
26     TreeNode* KthNode (TreeNode* pRoot, int k){
27         if(pRoot == nullptr || k <=0){
28             return nullptr;
29         }
30         if(!s){
31             MS(pRoot,k);
32         }
33         if(s>=k){
34             return res;
35         }
36         return nullptr;
37     }
38     void MS(TreeNode* root, int &k){
39         if(root == nullptr){
40             return;
41         }
42         MS(root->left,k);
43         ++s;
44         if(s==k){
45             res = root;
46         }
47         if(s>k){
48             return;
49         }
50         MS(root->right,k);
51     }
52 private:
53     int s = 0;
54     TreeNode *res = nullptr;
55 };