Как я могу поддерживать состояние между рекурсии вызовов

Question

Вот вопрос, который я пытаюсь решить: Найти -й наименьшее целое число в двоичное дерево поиска:

мой алгоритм: Я сделать заказовМои обход в BST. Каждый раз, когда я посещаю узел, я уменьшаю k на 1, а когда k = 0, я должен быть в k-м наименьшем узле.

Вот моя реализация:

void FindKthSmallest(struct TreeNode* root, int k) 
{ 
    if (root == NULL) return; 
    if (k== 0) return; 
    FindKthSmallest (root->left, k); 
    k--; 
    if (k == 0) 
    { 
    cout << root->data; 
    return; 
    } 
    FindKthSmallest (root->right, k); 
} 

Однако с такой реализацией, я вижу, что состояние к не может поддерживаться между рекурсивными вызовами.

Я думаю, что состояние k необходимо поддерживать в двух сценариях: рекурсивный вызов возвращается между дочерним и родительским и рекурсивными вызовами между родителем и дочерним - вот где я боюсь. Есть ли способ поддерживать состояние в таком сценарии?

Answer 1

В своей реализации, вы используете переменную k передать два различных часть информации:

1. Оставшееся количество узлов, прежде чем целевой узел найден.
2. Если целевой узел уже найден.

Чего не хватает на самом деле просто 2. Вы можете достичь этого:

I) Передача k в качестве ссылки вместо значения.

ii) Назначить значение 2.) выше значением 0 от k.

Результат будет выглядеть так:

void FindKthSmallest(struct TreeNode* root, int& k) 
{ 
    if (root == NULL) return; 
    if (k == 0) return; // k==0 means target node has been found 
    FindKthSmallest (root->left, k); 

    if (k > 0) // k==0 means target node has been found 
    { 
    k--; 
    if (k == 0) { // target node is current node 
     cout << root->data; 
     return; 
    } else { 
     FindKthSmallest (root->right, k); 
    } 
    } 
} 

Также обратите внимание, что выше реализация O(k). С BST вы можете добиться лучшей производительности для поиска k-th наименьшего целого числа.