226. Инвертировать двоичное дерево || Литкод

Учитывая root бинарного дерева, инвертировать дерево и вернуть его корень.

Пример 1:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Пример 2:

Input: root = [2,1,3]
Output: [2,3,1]

Пример 3:

Input: root = []
Output: []

Ограничения:

• Количество узлов в дереве находится в диапазоне [0, 100].
• -100 <= Node.val <= 100

Решение:-

Интуиция

В этом вопросе мы должны инвертировать бинарное дерево.
Поэтому мы используем Обход пост-порядка, в котором сначала мы идем в левое поддерево. а затем в Правом поддереве возвращаемся к Родительскому узлу.
Когда мы возвращаемся к родительскому узлу, мы меняем местами его Левое поддерево и Правое поддерево.

Подход

Сложность

• Временная сложность: O(N)
• Сложность пространства: O(N) Рекурсивное пространство стека

Код

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        // Base Case
        if(root==NULL)
            return NULL;
        invertTree(root->left); //Call the left substree
        invertTree(root->right); //Call the right substree
        // Swap the nodes
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;
        return root; // Return the root
    }
};