【剣指offer】面接問題54:二叉検索ツリーのK番目のノード【C++バージョン】

総括した部分のテーマの構想とコードは、完備しなければならない.【剣指offer-第2版】部分テーマと解答【C++バージョン】
タイトル:
二叉探索木を1本指定し、K番目に大きいノードを見つけてください.ツリーのノードは次のように定義されます.

struct treeNode {
       int val;
       treeNode *left;
       treeNode *right;
       treeNode(int x) :val(x), left(NULL), right(NULL) {}
};

問題解決の考え方:
1.二叉探索木の中序遍歴結果は1つの秩序ある配列であるので、二叉探索木の中序遍歴結果を求めることができれば、そのK番目に大きいノード2を求めることができる.注意中序遍歴の再帰と非再帰の方法はすべて掌握しなければならない
可AC的解法:使用再帰【C++版本】

#include 
#include 
#include 
using namespace std;
struct treeNode {
       int val;
       treeNode *left;
       treeNode *right;
       treeNode(int x) :val(x), left(NULL), right(NULL) {}
};
void inorder(treeNode *root);
void inorderByStack(treeNode *root);
treeNode *inorder(treeNode *root, int &k);
treeNode* KthNode(treeNode* pRoot, int k);
int main() {
       //  
       treeNode *root = &treeNode(5);
       treeNode *node1 = &treeNode(3);
       treeNode *node2 = &treeNode(7);
       root->left = node1;
       root->right = node2;
       treeNode *node3 = &treeNode(2);
       treeNode *node4 = &treeNode(4);
       treeNode *node5 = &treeNode(6);
       treeNode *node6 = &treeNode(8);
       node1->left = node3;
       node1->right = node4;
       node2->left = node5;
       node2->right = node6;
       int a = 4;
       treeNode * resu = KthNode(root,a);
       cout << resu->val << endl;
       system("pause");
       return 0;
}

treeNode* KthNode(treeNode* pRoot, int k)
{
     return inorder(pRoot, k);
}

//        53
treeNode *inorder(treeNode *root, int &k) {
       if (root == NULL)return NULL;
       treeNode *resu = NULL;

       resu = inorder(root->left, k);

       if (k == 1) {
              resu = root;         //           
       }      
       k--;
       if(k > 0)
              resu = inorder(root->right, k);
       return resu;
}

AC可能な方法:非再帰

//     
//       KthNode  
treeNode* KthNode(treeNode* pRoot, int k) {
       if (pRoot == NULL)return NULL;
       treeNode *tmp = pRoot,*resu = NULL;
       stack nodeStack;
       while (tmp != NULL || !nodeStack.empty()) {
              if (tmp != NULL) {
                     nodeStack.push(tmp);
                     tmp = tmp->left;
              }
              else {
                     tmp = nodeStack.top();
                     nodeStack.pop();
                     k--;
                     if (k == 0)
                           return tmp;
                     tmp = tmp->right;
              }
       }
       return NULL;
}

補足:ツリー内のシーケンス遍歴の再帰的および非再帰的メソッド

//    
void inorder(treeNode *root) {
    if (root == NULL)return;

    inorder(root->left);

    cout << root->val << endl;

    inorder(root->right);
}

//        
void inorderByStack(treeNode *root) {
    treeNode *tmp = root;

    stack nodeStack;
    while (tmp != NULL || !nodeStack.empty()) {
        if (tmp != NULL) {
            nodeStack.push(tmp);
            tmp = tmp->left;
        }
        else {
            tmp = nodeStack.top();
            cout << tmp->val << endl;
            nodeStack.pop();
            tmp = tmp->right;
        }
    }
}