1 Тема від Teg Miles

  • Teg Miles
  • Teg Miles
  • Користувач
  • Поза форумом
  • Дата реєстрації: 20.01.2016
  • Повідомлень: 473
    • Репутація: 84

Тема: Визначення максимальної глибини бінарного дерева

Знову завдання з LeetCode.
Ось рішення:

class Solution {
    int get_max_depth(TreeNode* root) {
        if (root != nullptr) {
            int left_depth = get_max_depth(root->left);
            int right_depth = get_max_depth(root->right);
            if (left_depth > right_depth) {
                return (left_depth + 1);
            }
            else {
                return (right_depth + 1);
            }
        }
        else {
            return 0;
        }
    }
public:
    int maxDepth(TreeNode* root) {
        int answer = get_max_depth(root);
        return answer;
    }
};

Загальний принцип мені зрозумілий,
але я не розумію як накопичується значення змінних left_depth і right_depth.
Звісно, там є рекурсивний виклик функції, але немає додавання абощо.
Як працює підрахунок змінних int у цьому випадку?

2 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 602
    • Репутація: 13310

Re: Визначення максимальної глибини бінарного дерева

А +1 це вже не "абощо"?

int get_max_depth(TreeNode* root) {
    return root == nullptr 
                  ? 0 
                  : 1 + std::max(get_max_depth(root->left), get_max_depth(root->right));
}
Подякували: leofun011

koala вебсайт

3 Відповідь від Teg Miles

  • Teg Miles
  • Teg Miles
  • Користувач
  • Поза форумом
  • Дата реєстрації: 20.01.2016
  • Повідомлень: 473
    • Репутація: 84

Re: Визначення максимальної глибини бінарного дерева

koala написав:

А +1 це вже не "абощо"?

int get_max_depth(TreeNode* root) {
    return root == nullptr 
                  ? 0 
                  : 1 + std::max(get_max_depth(root->left), get_max_depth(root->right));
}

Але return має закінчувати виклик функції та стоїть вже після рекурсії в моєму коді.

4 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 602
    • Репутація: 13310

Re: Визначення максимальної глибини бінарного дерева

Teg Miles написав:

Але return має закінчувати виклик функції та стоїть вже після рекурсії в моєму коді.

return - інструкція, що завершує функцію (а не "має завершувати"); завершення функції - це дія return, так само, як додавання - це дія оператора +.
Якщо return стоїть перед якимись іншими інструкціями, то ті інструкції не будуть виконані, бо, ще раз, return завершить функцію. Тому очевидно, що return буде йти після інших інструкцій, а не перед ними.
Тобто весь ваш коментар - ні про що; ви щось інше хотіли сказати.

Здається, ви трохи не так розумієте процес виконання складних виразів. Складні вирази мають свою послідовність обчислення, еквівалентну послідовності простих. Наприклад,

return 2 * ( 3 + 4 );

означає те саме, що

t1 = 3 + 4;
t2 = 2 * t1;
return t2;

Тобто множення і додавання виконуються до return. Я навіть більше скажу - комп'ютер саме так і виконує вашу програму, по одній операції з проміжними значеннями.

Спробуйте розписати мій (явно надмірно) складний вираз як комбінацію простих - і побачите щось дуже схоже на ваш код.

Подякували: Teg Miles1

koala вебсайт

5 Відповідь від leofun01

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 277
    • Репутація: 2720

Re: Визначення максимальної глибини бінарного дерева

Teg Miles написав:
return (left_depth + 1);
return (right_depth + 1);

.. немає додавання ..

та ладно

▼код (C++)
struct Solution {
    int maxDepth(TreeNode *x) {
        if(!x) return 0;
        int l = maxDepth(x->left),
            r = maxDepth(x->right);
        return (l < r ? r : l) + 1;
    }
};

leofun01 вебсайт

6 Відповідь від Teg Miles

  • Teg Miles
  • Teg Miles
  • Користувач
  • Поза форумом
  • Дата реєстрації: 20.01.2016
  • Повідомлень: 473
    • Репутація: 84

Re: Визначення максимальної глибини бінарного дерева

leofun01 написав:
Teg Miles написав:
return (left_depth + 1);
return (right_depth + 1);

.. немає додавання ..

та ладно

▼код (C++)
struct Solution {
    int maxDepth(TreeNode *x) {
        if(!x) return 0;
        int l = maxDepth(x->left),
            r = maxDepth(x->right);
        return (l < r ? r : l) + 1;
    }
};

Мав на увазі, що  тут немає, бо неправильно розумів виконання інструкцій компілятором:

int left_depth = get_max_depth(root->left);
int right_depth = get_max_depth(root->right);
Подякували: leofun011