226. Invert Binary Tree
Invert a binary tree.
to
226. Инвертирование бинарного дерева
Инвертируйте бинарное дерево.
в
// C++
/**
*
Definition for a binary tree node.
* struct
TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL),
right(NULL) {}
* };
*/
class Solution {
public:
TreeNode*
invertTree(TreeNode* root) {
}
};
// Java
/**
*
Definition for a binary tree node.
* public class TreeNode {
* int
val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode invertTree(TreeNode root) {
}
}
РЕШЕНИЕ
структуры данных - деревья
Анализ алгоритма
Если root = NULL, то инвертированным для пустого дерева будет
пустое.
Далее для каждой вершины следует переставить местами левого и правого
сына. То есть root -> left присвоить инвертированное правое поддерево, а root -> right
присвоить инвертированное левое поддерево.
Реализация алгоритма
class Solution
{
public:
TreeNode*
invertTree(TreeNode* root)
{
if (root == NULL) return
root;
TreeNode* temp =
root->left;
root->left =
invertTree(root->right);
root->right = invertTree(temp);
return root;
}
};
Java реализация
public class
Solution
{
public TreeNode invertTree(TreeNode root)
{
if (root == null) return
root;
TreeNode temp =
root.left;
root.left =
invertTree(root.right);
root.right =
invertTree(temp);
return root;
}
}