интуитивный способ понять дерева рекурсии - Напишите код, чтобы проверить, если бинарное дерево сбалансировано

Question

Вопрос:

Реализовать функцию, чтобы проверить, если бинарное дерево сбалансировано (то есть не два узла не отличаются по высоте от корня более чем на 1).

Решение:

int maxDepth(Node *root) 
{ 
    if(!root) return 0; 

    return 1 + max(maxDepth(root->left), maxDepth(root->right)); 
} 
int minDepth(Node *root) 
{ 
    if(!root) return 0; 

    return 1 + min(minDepth(root->left), minDepth(root->right)); 
} 
bool isBalanced(Node *root) 
{ 
    return maxDepth(root)-minDepth(root) <= 1; 
} 

Может кто-то помочь мне понять интуицию за этим решением? Я изо всех сил стараюсь «видеть» рекурсию за алгоритмами дерева. Я знаю, что maxDepth и minDepth должны найти высоту узла максимальной глубины и минимальной глубины в дереве, соответственно, но я не понимаю, как работает рекурсия.

Что еще более важно, я не совсем понимаю, как я мог придумать это решение самостоятельно. Поэтому были бы весьма полезны любые советы о том, как подойти к древовидным проблемам в целом.

Answer 1

Лучший способ понять, рассмотрим пример:

a 
/\ 
b c 
    /\ 
    d e 

при вызове maxDepth на корневой узел «а», что будет следующий код делать?

return 1 + max(maxDepth(root->left), maxDepth(root->right)); 

вернет 1 + макс из maxDepth('b') или maxDepth('c')

maxDepth('b') вернется 1, потому что:

1 + max(maxDepth(NULL), maxDepth(NULL)) = 1 + (max (0,0)) = 1 + 0 = 0; 

выше получает NULL с от 'Ъ' -> левый и 'b' -> правый

так, возвращаясь к maxDepth ('а'), теперь мы знаем, что она возвращает:

maxDepth('a') = 1 + max(1, maxDepth('c')); 

maxDepth('c') будут следовать те же шаги и вернуться 2. Следовательно:

maxDepth('a') = 1 + max(1, 2) = 1 + 2 = 3 

для minDepth() поток тот же самый с единственной разницей в использовании мин.() вместо max().