текст перекладу
Дерево — це популярна структура даних, яка є нелінійною за своєю природою. На відміну від інших структур даних, таких як масив, стек, черга та зв'язаний список, які є лінійними, дерево представляє ієрархічну структуру, що складається з вузлів, з кореневим вузлом зверху і дочірніми вузлами, з'єднаними за допомогою ребер.

Дерево містить вузли та 2 вказівники. Ці 2 вказівники — це лівий та правий дочірні вузли батьківського вузла.

Корінь: Корінь дерева — це найвищий вузол дерева, який не має батьківського вузла. У кожному дереві є лише один корінь.

Ребро: Ребро виступає як зв'язок між батьківським вузлом та дочірнім вузлом.

Лист: Вузол, який не має дочірніх вузлів, відомий як листовий вузол. Це останній вузол дерева. У дереві може бути кілька листових вузлів.

Глибина: Глибина вузла — це відстань від кореневого вузла до цього конкретного вузла.

Висота: Висота вузла — це відстань від цього вузла до найглибшого вузла дерева.

Висота дерева: Висота дерева — це максимальна висота будь-якого вузла.

4  
 / \  
 7 2 В бінарному дереві кожен вузол може м  
 6 9 1 3

Перехід по дереву в бінарних деревах:

Перехід — це спосіб відвідування всіх вузлів дерева в певному порядку.

Перехід в попередньому порядку: корінь → лівий дочірній вузол → правий дочірній вузол

void preorder(TreeNode* root){  
 if(root == NULL) return;  
 cout << root->val << " ";  
 preorder(root->left);  
 preorder(root->right);  
}

Перехід в порядку обробки: лівий дочірній вузол → корінь → правий дочірній вузол

void inorder(TreeNode* root){  
 if(root == NULL) return;  
 inorder(root->left);  
 cout << root->val << " ";  
 inorder(root->right);  
}

Перехід в зворотньому порядку: лівий дочірній вузол → правий дочірній вузол → корінь

void postorder(TreeNode* root){  
 if(root == NULL) return;  
 postorder(root->left);  
 postorder(root->right);  
 cout << root->data << " ";  
}

Перехід по рівнях (пошук в ширину): Перехід по дереву рівень за рівнем, використовуючи чергу.

Рівень 0 1 Перехід в попередньому порядку: 1, 2, 4, 5, 3, 6, 7  
 / \  
Рівень 1 2 3 Перехід в порядку обробки: 4, 2, 5, 1, 6, 3, 7  
 / \ / \  
Рівень 2 4 5 6 7 Перехід в зворотньому порядку: 4, 5, 2, 6, 7, 3, 1

Кроки:

1. Push (1) → Перевірити наявність лівого/правого дочірнього вузла → якщо є, то спочатку додати лівий, потім правий дочірній вузол в кінець (2, 3)
2. Тепер Pop(1) → потім pop null, як null — це кінець рівня 0.
3. Тепер аналізуємо рівень 1, якщо він не порожній, додати NULL знову в кінець.
4. Pop (2) → Перевірити наявність лівого/правого дочірнього вузла → якщо є, то додати лівий та правий дочірні вузли в кінець (4, 5)
5. Pop (3) → Перевірити наявність лівого/правого дочірнього вузла → якщо є, то додати лівий та правий дочірні вузли в кінець (6, 7)
6. Pop NULL → рівень 1 закінчено, перевірити, чи не порожній — додати NULL знову в кінець.
7. Pop (4) → Перевірити наявність лівого/правого дочірнього вузла → якщо ні, то просто вивести його в результат.
8. Pop (5) → Перевірити наявність лівого/правого дочірнього вузла → якщо ні, то просто вивести його в результат.
9. Pop (6) → Перевірити наявність лівого/правого дочірнього вузла → якщо ні, то просто вивести його в результат.
10. Pop (7) → Перевірити наявність лівого/правого дочірнього вузла → якщо ні, то просто вивести його в результат.
11. Pop NULL → рівень 2 закінчено → черга порожня, вихід.

void LevelOrderTraversal(TreeNode* root){  
 if(root == NULL) return;  
 queue<TreeNode*> q;  
 q.push(root);  
 q.push(NULL);  
 while(!q.empty()){  
 TreeNode* node = q.front();  
 q.pop();  
 cout << node->val <<" ";  
 if(node->left) q.push(node->left);  
 if(node->right) q.push(node->right);  
 }  
}

Побудова дерева з переходів

Побудова дерева з переходів попередньому порядку та порядку обробки

Підхід:

1. Вибрати елемент з попереднього порядку і створити вузол.
2. Інкрементувати індекс попереднього порядку
3. Знайти позицію вибраного елемента в порядку обробки.
4. Виклик побудови лівого піддерева з порядку обробки (від 0 до позиції - 1).
5. Виклик побудови правого піддерева з порядку обробки (від позиції + 1 до n).
   6.
   текст перекладу
   Повертання до вузла.

int Search(int inorder[], int start, int end, int curr){  
 for(int i= start; i<=end; i++){  
 if(inorder[i] == curr){  
 return i;  
 }  
 }  
 return -1;  
}  
TreeNode* buildTree(int preorder[], int inorder[], int start, int end){  
 static int idx = 0;  
 if(start > end) return NULL;  
 int curr = preorder[idx++];  
 TreeNode* node = new Node(curr);  
 if(start == end) return node; // повернути піддерево   
 int pos = Search(inorder, start, end, curr);  
 node->left = buildTree(preorder, inorder, start, pos-1);  
 node->right = buildTree(preorder, inorder, pos+1, end);  
 return node;  
}

Побудова дерева з переходів пост-обробки та порядку обробки

Підхід:

1. Почніть з кінця пост-обробки та виберіть один елемент для створення вузла.
2. Зменшіть індекс пост-обробки.
3. Знайдіть позицію вибраного елемента в порядку обробки.
4. Викликати побудову правого піддерева з порядку обробки (позиція+1 до n).
5. Викликати побудову лівого піддерева з порядку обробки (0 до позиції-1).
6. Повернути вузол.

int Search(int inorder[], int start, int end, int curr){  
 for(int i= start; i<=end; i++){  
 if(inorder[i] == curr){  
 return i;  
 }  
 }  
 return -1;  
}  
TreeNode* buildTree(int postorder[], int inorder[], int start, int end){  
 static int idx = postorder.size();  
 if(start > end) return NULL;  
 int curr = postorder[idx--];  
 TreeNode* node = new Node(curr);  
 if(start == end) return node; // повернути піддерево   
 int pos = Search(inorder, start, end, curr);  
 node->right = buildTree(postorder, inorder, pos+1, end);  
 node->left = buildTree(postorder, inorder, start, pos-1);  
 return node;  
}  
// Складність часу : O(n)  
// Просторова складність : O(n)

Бінарне дерево пошуку (BST)

Бінарне дерево пошуку — це структура даних, що базується на вузлах і має такі властивості:

• Ліве піддерево містить лише вузли з меншими значеннями, ніж корінь.
• Праве піддерево містить лише вузли з більшими значеннями, ніж корінь.
• Ліве та праве піддерево також повинні бути бінарним деревом пошуку. Не повинно бути дубльованих вузлів.

Побудова BST з масиву

TreeNode* insertIntoBST(TreeNode* root, int val){  
 if(!root) return new TreeNode(val);  
 if(val < root->data){  
 root->left = insertIntoBST(root->left, val);  
 }  
 else{  
 root->right = insertIntoBST(root->right, val);  
 }  
 return root;  
}  

TreeNode* buildBSTFromArray(vector& arr){  
 TreeNode* root = nullptr;  
 for(int val : arr){  
 root = insertIntoBST(root, val);  
 }  
 return root;  
}  
// Складність часу : O(nlogn)  
// Просторова складність : O(n)

Запит 1 Інвертування бінарного дерева

Дано root бінарного дерева, інвертуйте дерево та поверніть його корінь.

Приклад 1:

Вхід: root = [4,2,7,1,3,6,9]  
Вихід: [4,7,2,9,6,3,1]

Приклад 2:

Вхід: root = [2,1,3]  
Вихід: [2,3,1]

Приклад 3:

Вхід: root = []  
Вихід: []

Підхід

4  
 / \  
 2 7  
 / \ / \  
 1 3 6 9

Ми починаємо з кореневого вузла (= 4). Спочатку перевіряємо, чи є поточний вузол порожнім.

Якщо ні, обмінюємо лівий та правий дочірні вузли. Тепер дерево повинно виглядати так:

4  
 / \  
 7 2  
 / \ / \  
 6 9 1 3

Переміщаємося на ліву сторону. Тепер ми на вузлі 7. Перевіряємо, чи є поточний вузол порожнім. Він не порожній, тому міняємо місцями лівий дочірній вузол (= вузол 6) та правий дочірній вузол (= вузол 9)

4  
 / \  
 7 2  
 / \ / \  
 9 6 1 3

Переміщаємося на ліву сторону. Тепер ми на вузлі 9 і перевіряємо, чи є поточний вузол порожнім. Він не порожній, тому міняємо місцями лівий дочірній вузол (= null) та правий дочірній вузол (= null). Тепер ми маємо таке саме дерево, як вище.

Переміщаємося на ліву сторону. Тепер ми на null вузлі, тому повертаємося до вузла 9 і переміщаємося на праву сторону. Тепер ми на null вузлі, тому повертаємося до вузла 9. Ми вже перевірили вузол 9, тому повертаємося до вузла 7, переміщаємося на праву сторону.
текст перекладу
Тепер ми на вузлі 6.

Пропускаю пояснення для вузла 6, оскільки нічого не відбудеться.

Після цього повертаємося до вузла 7 і повертаємося до вузла 4, потім йдемо праворуч. Тепер ми на вузлі 2. Поточний вузол не є порожнім, тому міняємо місцями лівий дочірній вузол (= вузол 1) та правий дочірній вузол (= в / \
9 6 3 1
``

Тепер переміщаємося на ліву сторону. Тепер ми на вузлі 3.

Пропускаю решту пояснення. Нічого не відбудеться. Наприкінці повертаємося до вузла 4 і завершуємо перехід по всіх вузлах.

Ми повинні повернути:

4  
 / \  
 7 2  
 / \ / \  
 9 6 3 1

class Solution {  
public:  
 TreeNode* invertTree(TreeNode* root) {  
 if(root == nullptr){  
 return nullptr;  
 }  
 TreeNode* temp = root->left;  
 root->left = root->right;  
 root->right = temp;  
 invertTree(root->left);  
 invertTree(root->right);  
 return root;  
 }  
};  

// Складність часу: O(N)  
// Просторова складність: O(logN) (збалансоване дерево)

Приклад 2 Максимальна глибина бінарного дерева

Дано root бінарного дерева, поверніть його максимальну глибину.

Максимальна глибина бінарного дерева — це кількість вузлів на найдовшому шляху від кореневого вузла до найвіддаленішого листа.

Приклад 1:

Вхід: root = [3,9,20,null,null,15,7]  
Вихід: 3

Приклад 2:

Вхід: root = [1,null,2]  
Вихід: 2

Підхід:

1. Якщо дерево порожнє, поверніть -1.
2. Інакше: отримайте максимальну глибину лівого піддерева рекурсивно, тобто викликайте maxDepth(дерево → ліве-піддерево). Отримайте максимальну глибину правого піддерева рекурсивно, тобто викликайте maxDepth(дерево → праве-піддерево).
3. Отримайте максимум з максимальної глибини лівого та правого піддерева і додайте 1 для поточного вузла. max_depth = max (макс. глибина лівого піддерева, макс. глибина правого піддерева) + 1
4. Поверніть max_depth

class Solution {  
public:  
 int maxDepth(TreeNode* root) {  
 if(root == NULL){  
 return 0;  
 }  
 int LHeight = maxDepth(root->left);  
 int RHeight = maxDepth(root->right);  
 return max(LHeight, RHeight) + 1;  
 }  
};  

// Складність часу: O(N)  
// Просторова складність: O(logN) (збалансоване дерево)

Приклад 3 Збалансоване бінарне дерево

Дано бінарне дерево, визначте, чи є воно збалансованим за висотою.

Приклад 1:

Вхід: root = [3,9,20,null,null,15,7]  
Вихід: true

Приклад 2:

Вхід: root = [1,2,2,3,3,null,null,4,4]  
Вихід: false

Приклад 3:

Вхід: root = []  
Вихід: true

Підхід:

Щоб визначити, чи є бінарне дерево збалансованим за висотою:

Визначення збалансованого дерева за висотою: Бінарне дерево є збалансованим за висотою, якщо:

• Різниця висоти лівого та правого піддерев не перевищує 1.
• Ліве та праве піддерева також є збалансованими за висотою.

Рекурсивний підхід:

Використовуйте допоміжну функцію, яка обчислює висоту піддерева та перевіряє на баланс.
текст перекладу
Тепер ми на вузлі 6.

Пропускаю пояснення для вузла 6, оскільки нічого не відбудеться.

Після цього повертаємося до вузла 7 і повертаємося до вузла 4, потім йдемо праворуч. Тепер ми на вузлі 2. Поточний вузол не є порожнім, тому міняємо місцями лівий дочірній вузол (= вузол 1) та правий дочірній вузол (= вузол 3).

4  
 / \  
 7 2  
 / \ / \  
 9 6 3 1

Тепер переміщаємося на ліву сторону. Тепер ми на вузлі 3.

Пропускаю решту пояснення. Нічого не відбудеться. Наприкінці повертаємося до вузла 4 і завершуємо перехід по всіх вузлах.

Ми повинні повернути:

4  
 / \  
 7 2  
 / \ / \  
 9 6 3 1

class Solution {  
public:  
 TreeNode* invertTree(TreeNode* root) {  
 if(root == nullptr){  
 return nullptr;  
 }  
 TreeNode* temp = root->left;  
 root->left = root->right;  
 root->right = temp;  
 invertTree(root->left);  
 invertTree(root->right);  
 return root;  
 }  
};  

// Складність часу: O(N)  
// Просторова складність: O(logN) (збалансоване дерево)

Приклад 2 Максимальна глибина бінарного дерева

Дано root бінарного дерева, поверніть його максимальну глибину.

Максимальна глибина бінарного дерева — це кількість вузлів на найдовшому шляху від кореневого вузла до найвіддаленішого листа.

Приклад 1:

Вхід: root = [3,9,20,null,null,15,7]  
Вихід: 3

Приклад 2:

Вхід: root = [1,null,2]  
Вихід: 2

Підхід:

1. Якщо дерево порожнє, поверніть -1.
2. Інакше: отримайте максимальну глибину лівого піддерева рекурсивно, тобто викликайте maxDepth(дерево → ліве-піддерево). Отримайте максимальну глибину правого піддерева рекурсивно, тобто викликайте maxDepth(дерево → праве-піддерево).
3. Отримайте максимум з максимальної глибини лівого та правого піддерева і додайте 1 для поточного вузла. max_depth = max (макс. глибина лівого піддерева, макс. глибина правого піддерева) + 1
4. Поверніть max_depth

class Solution {  
public:  
 int maxDepth(TreeNode* root) {  
 if(root == NULL){  
 return 0;  
 }  
 int LHeight = maxDepth(root->left);  
 int RHeight = maxDepth(root->right);  
 return max(LHeight, RHeight) + 1;  
 }  
};  

// Складність часу: O(N)  
// Просторова складність: O(logN) (збалансоване дерево)

Приклад 3 Збалансоване бінарне дерево

Дано бінарне дерево, визначте, чи є воно збалансованим за висотою.

Приклад 1:

Вхід: root = [3,9,20,null,null,15,7]  
Вихід: true

Приклад 2:

Вхід: root = [1,2,2,3,3,null,null,4,4]  
Вихід: false

Приклад 3:

Вхід: root = []  
Вихід: true

Підхід:

Щоб визначити, чи є бінарне дерево збалансованим за висотою:

Визначення збалансованого дерева за висотою: Бінарне дерево є збалансованим за висотою, якщо:

• Різниця висоти лівого та правого піддерев не перевищує 1.
• Ліве та праве піддерева також є збалансованими за висотою.

Рекурсивний підхід:

Використовуйте допоміжну функцію, яка обчислює висоту піддерева та перевіряє на баланс.
текст перекладу
Дерево tree також може вважатися піддеревом самого себе.

Приклад 1:

Вхід: root = [3,4,5,1,2], subRoot = [4,1,2]  
Вихід: true

Приклад 2:

Вхід: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]  
Вихід: false

Підхід:

• Використовуйте допоміжну функцію (isIdentical), щоб порівняти, чи є два дерева (root та subRoot) ідентичними.
• Використовуйте рекурсію в основній функції (isSubtree), щоб пройти по дереву root і перевірити збіги з subRoot.

Кроки для порівняння двох дерев (isIdentical):

• Якщо обидва вузли — це nullptr, вони ідентичні; повернути true.
• Якщо один вузол є nullptr або їх значення не збігаються, повернути false.
• Рекурсивно порівнюйте ліві та праві піддерева обох дерев.

Кроки для перевірки піддерева (isSubtree):

• Якщо subRoot є nullptr, це завжди піддерево (повертає true).
• Якщо root є nullptr, але subRoot не є, повертає false.
• Перевірте, чи є root і subRoot ідентичними за допомогою isIdentical.
• Якщо ні, рекурсивно перевірте ліві та праві піддерева root на наявність збігів з subRoot.

Рекурсивний обхід:

• Використовуйте обхід попереднім порядком (відвідати root спочатку, потім ліві та праві піддерева) для пошуку можливого збігу в root.

class Solution {  
public:  
 // Допоміжна функція для перевірки, чи є два дерева ідентичними  
 bool isIdentical(TreeNode* p, TreeNode* q) {  
 if (!p && !q) return true; // Обидва вузли є null  
 if (!p || !q) return false; // Один вузол є null  
 if (p->val != q->val) return false; // Значення не збігаються  
 // Рекурсивно перевірити ліві та праві піддерева  
 return isIdentical(p->left, q->left) && isIdentical(p->right, q->right);  
 }  

 // Основна функція для перевірки, чи є subRoot піддеревом root  
 bool isSubtree(TreeNode* root, TreeNode* subRoot) {  
 if (!subRoot) return true; // Порожнє дерево завжди є піддеревом  
 if (!root) return false; // Непорожнє дерево не може бути піддеревом порожнього дерева  
 if (isIdentical(root, subRoot)) return true; // Перевірити, чи є дерева ідентичними  
 // Рекурсивно перевірити ліві та праві піддерева  
 return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);  
 }  
};  

// Складність часу: O(m * n)  
// Просторова складність: O(h1 + h2)

Приклад 6 Найближчий спільний предок бінарного дерева пошуку

Дано бінарне дерево пошуку (BST), знайдіть найнижчий спільний предок (LCA) двох заданих вузлів у BST.

Згідно з визначенням LCA на Wikipedia: “Найнижчий спільний предок визначається між двома вузлами p та q як найнижчий вузол в T, який має обидва p та q як нащадків (де дозволено, щоб вузол був нащадком самого себе).”

Приклад 1:

Вхід: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8  
Вихід: 6  
Пояснення: Найнижчий спільний предок вузлів 2 та 8 — це 6.

Приклад 2:

Вхід: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4  
Вихід: 2  
Пояснення: Найнижчий спільний предок вузлів 2 та 4 — це 2, оскільки вузол може бути нащадком самого себе згідно з визначенням LCA.

Приклад 3:

Вхід: root = [2,1], p = 2, q = 1  
Вихід: 2

Структура бінарного дерева:

• Бінарне дерево подібне до сімейного дерева, але замість членів сім'ї воно містить вузли.
  текст перекладу
  Кожен вузол може мати не більше двох дітей:
• лівий дитина та правий дитина.
• Корінь дерева є як «дідусь» вгорі.

6  
 / \  
 2 8  
 / \ \  
 0 4 9  
 / \  
 3 5

• Предок вузла — це будь-який вузол, що знаходиться на шляху від вузла до кореня.
• Для вузла 5, його предками є: 4 (батько), 2 (дідусь), 6 (корінь)
• Для двох вузлів, скажімо 3 та 5, їх спільним предком є вузол, що з'являється на обох їхніх шляхах до кореня.
• У цьому дереві спільні предки для 3 та 5 це: 4, 2, 6
• Найнижчий спільний предок (LCA): серед усіх спільних предків, найнижчий спільний предок — це той, що найближчий до вузлів.
• Для вузлів 3 та 5, LCA — це 4, оскільки це найнижчий спільний предок для обох вузлів.
• Для вузлів 2 та 8, LCA — це 6, оскільки це перший вузол, де шляхи до 2 та 8 відходять.

Підхід:

1. Почати з кореня дерева пошуку.
2. Порівняти значення p і q з значенням поточного кореня:

• Якщо обидва менші, йдемо в ліве піддерево.
• Якщо обидва більші, йдемо в праве піддерево.
• Якщо вони знаходяться на різних сторонах (або один збігається з коренем), поточний корінь є LCA.

1. Зупинитися, коли знайдемо розгалуження або коли один вузол збігається з поточним коренем.

class Solution {  
public:  
 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {  
 while (root != nullptr) {  
 if (p->val > root->val && q->val > root->val) {  
 // І p, і q більші за корінь, рухаємося в праве піддерево  
 root = root->right;  
 } else if (p->val < root->val && q->val < root->val) {  
 // І p, і q менші за корінь, рухаємося в ліве піддерево  
 root = root->left;  
 } else {  
 // Поточний вузол — це LCA, оскільки p та q розходяться тут  
 return root;  
 }  
 }  
 return nullptr;  
 }  
};  

// Складність часу:  
// Збалансоване дерево пошуку: O(log n).  
// Похиле дерево пошуку: O(n).  
// Просторова складність: O(1).

Приклад 7 Правий бік вигляду бінарного дерева

Дано root бінарного дерева, уявіть, що ви стоїте з правого боку цього дерева, поверніть значення вузлів, які ви можете побачити, впорядковані з верхнього до нижнього рівня.

Приклад 1:

Вхід: root = [1,2,3,null,5,null,4]

Вихід: [1,3,4]

Пояснення:

Приклад 2:

Вхід: root = [1,2,3,4,null,null,null,5]

Вихід: [1,3,4,5]

Пояснення:

Приклад 3:

Вхід: root = [1,null,3]

Вихід: [1,3]

Приклад 4:

Вхід: root = []

Вихід: []

Підхід

Для знаходження вигляду з правого боку бінарного дерева:

1. Виконати обхід по рівнях за допомогою черги.
2. Для кожного рівня зберігати значення останнього вузла, оскільки він видимий з правого боку.
3. Повернути зібрані значення як результат.

Кроки

1. Перевірте, чи корінь є nullptr. Якщо так, поверніть порожній масив.
2. Використовуйте чергу для обходу бінарного дерева по рівнях.
3. На кожному рівні пройдіться через всі вузли та зберігайте значення останнього вузла на цьому рівні.
4. Повторюйте до обробки всіх рівнів.

class Solution {  
public:  
 vector rightSideView(TreeNode* root) {  
 vector result;  
 if(!root) return result;  
 queue q;  
 q.push(root);  
 while(!q.empty()){  
 int levelsize = q.size();  
 for(int i=0; i<levelsize; i++){  
 TreeNode* curr = q.front();  
 q.pop();  
 if(i == levelsize - 1) result.push_back(curr->val);  
 if(curr->left) q.push(curr->left);  
 if(curr->right) q.push(curr->right);  
 }  
 }  
 return result;  
 }  
};  

// Складність часу: O(N).  
// Просторова складність:  
 // Середній випадок: O(N).

текст перекладу
// Найгірший випадок: O(N).

Приклад 8 Перевірка бінарного дерева пошуку

Дано root бінарного дерева, визначте, чи є воно дійсним бінарним деревом пошуку (BST).

Дійсне BST визначається наступним чином:

• Ліве піддерево вузла містить лише вузли зі значеннями меншими за ключ цього вузла.
• Праве піддерево вузла містить лише вузли зі значеннями більшими за ключ цього вузла.
• Ліве та праве піддерево також повинні бути бінарними деревами пошуку.

Приклад 1:

Вхід: root = [2,1,3]  
Вихід: true

Приклад 2:

Вхід: root = [5,1,4,null,null,3,6]  
Вихід: false  
Пояснення: Значення кореня 5, але значення правої дитини 4.

Підхід: Властивості BST

Рекурсивна функція: Функція validate приймає три параметри:

• node: Поточний вузол, що перевіряється.
• minVal: Вказівник на вузол, що представляє мінімально допустиме значення для поточного вузла.
• maxVal: Вказівник на вузол, що представляє максимально допустиме значення для поточного вузла.

Ця функція забезпечує, щоб значення поточного вузла знаходилось між значеннями minVal і maxVal.

Базовий випадок:

• Якщо node є NULL, повертається true (порожнє дерево є дійсним BST).

Порівняння значень: Перевірте, чи порушує значення node->val обмеження:

node(minVal, maxVal)  
 / \   
left(minVal, node) right(node, maxVal)

• node->val має бути більшим за minVal->val (якщо minVal не NULL).
• node->val має бути меншим за maxVal->val (якщо maxVal не NULL).

Якщо будь-яка умова порушена, повертається false.

Рекурсивна перевірка: Рекурсивно перевіряйте ліве та праве піддерева з оновленими обмеженнями:

• Для лівого піддерева максимальне допустиме значення (maxVal) оновлюється до поточного вузла.
• Для правого піддерева мінімальне допустиме значення (minVal) оновлюється до поточного вузла.

Комбінування результатів: Вузол є дійсним тільки тоді, коли обидва піддерева є дійсними.

class Solution {  
public:  
 // Допоміжна функція для перевірки BST  
 bool validate(TreeNode* node, TreeNode* minVal = NULL, TreeNode* maxVal = NULL) {  
 // Базовий випадок: Порожній вузол завжди є дійсним BST  
 if (!node) return true;  

 // Перевірка, чи поточний вузол порушує обмеження min або max  
 // Якщо minVal не NULL, значення поточного вузла повинно бути більшим за значення minVal  
 if (minVal != NULL && node->val <= minVal->val) return false;  
 // Якщо maxVal не NULL, значення поточного вузла повинно бути меншим за значення maxVal  
 if (maxVal != NULL && node->val >= maxVal->val) return false;  

 // Рекурсивно перевіряємо ліве піддерево  
 // Для лівого піддерева оновлюємо максимальне значення до поточного вузла  
 bool leftValid = validate(node->left, minVal, node);  

 // Рекурсивно перевіряємо праве піддерево  
 // Для правого піддерева оновлюємо мінімальне значення до поточного вузла  
 bool rightValid = validate(node->right, node, maxVal);  

 // Поточне піддерево є дійсним тільки якщо обидва піддерева дійсні  
 return leftValid && rightValid;  
 }  

 // Основна функція для перевірки, чи є бінарне дерево дійсним BST  
 bool isValidBST(TreeNode* root) {  
 // Починаємо перевірку без обмежень (NULL min та max значення)  
 return validate(root, NULL, NULL);  
 }  
};  

// Складність часу: O(N).  
// Просторова складність:  
 // Середній випадок: O(logN).

текст перекладу
// Найгірший випадок: O(N).

Приклад 9 Підрахунок хороших вузлів у бінарному дереві

Дано бінарне дерево root, вузол X у дереві називається хорошим, якщо на шляху від кореня до X немає вузлів зі значенням, що більше за X.

Повернути кількість хороших вузлів у бінарному дереві.

Приклад 1:

Вхід: root = [3,1,4,3,null,1,5]  
Вихід: 4  
Пояснення: Вузли синього кольору — хороші.  
Корінь дерева (3) завжди є хорошим вузлом.  
Вузол 4 -> (3,4) є найбільшим значенням на шляху від кореня.  
Вузол 5 -> (3,4,5) є найбільшим значенням на шляху.  
Вузол 3 -> (3,1,3) є найбільшим значенням на шляху.

Приклад 2:

Вхід: root = [3,3,null,4,2]  
Вихід: 3  
Пояснення: Вузол 2 -> (3, 3, 2) не є хорошим, бо "3" більше за нього.

Приклад 3:

Вхід: root = [1]  
Вихід: 1  
Пояснення: Корінь вважається хорошим.

Підхід:

Ми використовуватимемо рекурсивний підхід (Пошук в глибину, DFS) для вирішення цієї задачі. На кожному кроці ми:

1. Зберігаємо максимальне значення, яке ми бачили на шляху від кореня.
2. Порівнюємо значення поточного вузла з цим максимальним значенням:

• Якщо значення вузла більше або дорівнює максимальному значенню, це хороший вузол.

1. Оновлюємо максимальне значення, коли рухаємося глибше в дерево.

2. Рекурсивно перевіряємо лівого та правого нащадка поточного вузла.

class Solution {  
public:  
 int countGN(TreeNode* root, int maxSoFar){  
 // Базовий випадок   
 if(root == nullptr) return 0;  
 // підраховуємо поточний вузол, якщо він хороший  
 int count = 0;  
 if(root->val >= maxSoFar) count++;  

 // Оновлюємо максимальне значення для шляху  
 maxSoFar = max(maxSoFar, root->val);  

 // Рекурсивно підраховуємо хороші вузли в лівому та правому піддереві  
 count += countGN(root->left, maxSoFar);  
 count += countGN(root->right, maxSoFar);  
 return count;  
 }  
 int goodNodes(TreeNode* root) {  
 return countGN(root, INT_MIN);  
 }  
};  

// Складність часу: O(N).  
// Просторова складність:   
 // Середній випадок: O(logN).  
 // Найгірший випадок: O(N).

Приклад 10 k-й найменший елемент у BST

Дано корінь бінарного дерева пошуку (BST) та ціле число k, повернути k-й найменший елемент (1-індексований) серед усіх значень вузлів у дереві.

Приклад 1:

Вхід: root = [3,1,4,null,2], k = 1  
Вихід: 1

Приклад 2:

Вхід: root = [5,3,6,2,4,null,null,1], k = 3  
Вихід: 3

Підхід:

Ми знаємо, що в BST: leftNode < root < rightNode. Тому, якщо ми здійснимо перехід по дереву в порядку зростання (inOrder Traversal), постійно рухаючись ліворуч, ми досягнемо найменшого значення дерева.

Перехід по дереву в порядку зростання (inOrder traversal) спочатку дасть перший найменший елемент, потім другий найменший елемент і так далі.
Отже, замість того, щоб зберігати значення вузлів у векторі, ми можемо використовувати змінну ‘count’, щоб відстежувати, чи досягли ми k-го найменшого елемента на шляху в порядку зростання.

class Solution {  
public:  
 int kthSmallest(TreeNode* root, int k) {  
 int count = 0;  
 TreeNode* result = nullptr;  
 inorder(root, k, count, result);  
 return result->val;  
 }  

 void inorder(TreeNode* root, int k, int& count, TreeNode*& result) {  
 if (!root) return;  
 inorder(root->left, k, count, result);  
 if (++count == k) result = root;  
 inorder(root->right, k, count, result);  
 }  
};  

// Складність часу: O(N).  
// Просторова складність: O(H), де H — висота дерева.

текст перекладу
// Найгірший випадок: O(N).

Приклад 9 Підрахунок хороших вузлів у бінарному дереві

Дано бінарне дерево root, вузол X у дереві називається хорошим, якщо на шляху від кореня до X немає вузлів зі значенням, що більше за X.

Повернути кількість хороших вузлів у бінарному дереві.

Приклад 1:

Вхід: root = [3,1,4,3,null,1,5]  
Вихід: 4  
Пояснення: Вузли синього кольору — хороші.  
Корінь дерева (3) завжди є хорошим вузлом.  
Вузол 4 -> (3,4) є найбільшим значенням на шляху від кореня.  
Вузол 5 -> (3,4,5) є найбільшим значенням на шляху.  
Вузол 3 -> (3,1,3) є найбільшим значенням на шляху.

Приклад 2:

Вхід: root = [3,3,null,4,2]  
Вихід: 3  
Пояснення: Вузол 2 -> (3, 3, 2) не є хорошим, бо "3" більше за нього.

Приклад 3:

Вхід: root = [1]  
Вихід: 1  
Пояснення: Корінь вважається хорошим.

Підхід:

Ми використовуватимемо рекурсивний підхід (Пошук в глибину, DFS) для вирішення цієї задачі. На кожному кроці ми:

1. Зберігаємо максимальне значення, яке ми бачили на шляху від кореня.
2. Порівнюємо значення поточного вузла з цим максимальним значенням:

• Якщо значення вузла більше або дорівнює максимальному значенню, це хороший вузол.

1. Оновлюємо максимальне значення, коли рухаємося глибше в дерево.

2. Рекурсивно перевіряємо лівого та правого нащадка поточного вузла.

class Solution {  
public:  
 int countGN(TreeNode* root, int maxSoFar){  
 // Базовий випадок   
 if(root == nullptr) return 0;  
 // підраховуємо поточний вузол, якщо він хороший  
 int count = 0;  
 if(root->val >= maxSoFar) count++;  

 // Оновлюємо максимальне значення для шляху  
 maxSoFar = max(maxSoFar, root->val);  

 // Рекурсивно підраховуємо хороші вузли в лівому та правому піддереві  
 count += countGN(root->left, maxSoFar);  
 count += countGN(root->right, maxSoFar);  
 return count;  
 }  
 int goodNodes(TreeNode* root) {  
 return countGN(root, INT_MIN);  
 }  
};  

// Складність часу: O(N).  
// Просторова складність:   
 // Середній випадок: O(logN).  
 // Найгірший випадок: O(N).

Приклад 10 k-й найменший елемент у BST

Дано корінь бінарного дерева пошуку (BST) та ціле число k, повернути k-й найменший елемент (1-індексований) серед усіх значень вузлів у дереві.

Приклад 1:

Вхід: root = [3,1,4,null,2], k = 1  
Вихід: 1

Приклад 2:

Вхід: root = [5,3,6,2,4,null,null,1], k = 3  
Вихід: 3

Підхід:

Ми знаємо, що в BST: leftNode < root < rightNode. Тому, якщо ми здійснимо перехід по дереву в порядку зростання (inOrder Traversal), постійно рухаючись ліворуч, ми досягнемо найменшого значення дерева.

Перехід по дереву в порядку зростання (inOrder traversal) спочатку дасть перший найменший елемент, потім другий найменший елемент і так далі.
Отже, замість того, щоб зберігати значення вузлів у векторі, ми можемо використовувати змінну ‘count’, щоб відстежувати, чи досягли ми k-го найменшого елемента на шляху в порядку зростання.

class Solution {  
public:  
 int kthSmallest(TreeNode* root, int k) {  
 int count = 0;  
 TreeNode* result = nullptr;  
 inorder(root, k, count, result);  
 return result->val;  
 }  

 void inorder(TreeNode* root, int k, int& count, TreeNode*& result) {  
 if (!root) return;  
 inorder(root->left, k, count, result);  
 if (++count == k) result = root;  
 inorder(root->right, k, count, result);  
 }  
};  

// Складність часу: O(N).  
// Просторова складність: O(H), де H — висота дерева.

текст перекладу
// Найгірший випадок: O(N) (спотворене дерево).

Якщо вам сподобалося це пояснення концепцій, будь ласка, підпишіться, слідкуйте та ставте "клас"

Перекладено з: Understanding Binary Tree in C++