10114. Tree Инвертирование

Дано бинарное дерево. Инвертируйте его. А именно для каждой вершины:

· левого сына сделайте правым;

· правого сына сделайте левым;

Определение дерева:

//Java

class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) {

val = x;

left = null;

right = null;

}

}

// C++

class TreeNode

{

public:

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

Реализуйте функцию Invert которая возвращает указатель на инвертированное дерево.

// Java

TreeNode Invert(TreeNode tree)

// C++

TreeNode* Invert(TreeNode *tree)

Пример

Функция Invert возвращает res – указатель на инвертированное дерево.

РЕШЕНИЕ

дерево

Анализ алгоритма

Если root = NULL, то инвертированным для пустого дерева будет пустое.

Далее для каждой вершины следует переставить местами левого и правого сына. То есть root → left присвоить инвертированное правое поддерево, а root → right присвоить инвертированное левое поддерево.

Реализация алгоритма

TreeNode* Invert(TreeNode* tree)

{

Если root = NULL, то инвертированным для пустого дерева будет пустое.

if (tree == NULL) return tree;

Меняем местами левого и правого сына.

TreeNode* temp = tree->left;

tree->left = Invert(tree->right);

tree->right = Invert(temp);

return tree;

}

Java реализация

TreeNode Invert(TreeNode tree)

{

if (tree == null) return tree;

TreeNode temp = tree.left;

tree.left = Invert(tree.right);

tree.right = Invert(temp);

return tree;

}