101. Symmrtric Tree

Given a binary tree, check whether it is a mirror of itself (i.e. symmetric around its center).

For example, this binary tree is symmetric:

But the following is not:

101. Симметричное дерево

Задано бинарное дерево. Проверьте, является ли оно зеркальным отображением самого себя (то есть является ли оно симметрическим относительно центра).

// C++

class Solution {

public:

bool isSymmetric(TreeNode* root) {

}

};

// Java

public class Solution {

public boolean isSymmetric(TreeNode root) {

}

};

РЕШЕНИЕ

структуры данных - деревья

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

Если root = NULL, то дерево симметрично. Иначе запускаем функцию Helper, которая проверяет, являются ли два дерева left и right симметрическими отображениями друг друга. Исходное дерево будет симметричным, если его левый и правый сын являются симметрическими отображениями друг друга.

Опишем работу функции Helper:

· Если left и right равны NULL, то деревья симметричны.

· Если одно из деревьев (left или right) равно NULL, а второе не NULL, то деревья не симметричны.

Для того чтобы деревья left и right были симметрическими отображениями друг друга, необходимо и достаточно чтобы:

· left -> val и right -> val были равны;

· симметрическими отображениями друг друга были left -> left и right -> right;

· симметрическими отображениями друг друга были left -> right и right -> left;

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

class Solution

{

public:

bool isSymmetric(TreeNode *root)

{

if(root == NULL)

return true;

return Helper(root->left,root->right);

}

bool Helper(TreeNode* left, TreeNode* right)

{

if(left == NULL && right == NULL)

return true;

else if(left == NULL || right == NULL)

return false;

bool cond1 = left->val == right->val;

bool cond2 = Helper(left->left,right->right);

bool cond3 = Helper(left->right, right->left);

return cond1 && cond2 && cond3;

}

};

Java реализация

public class Solution

{

public boolean isSymmetric(TreeNode root)

{

if(root == null)

return true;

return Helper(root.left,root.right);

}

boolean Helper(TreeNode left, TreeNode right)

{

if(left == null && right == null)

return true;

else if(left == null || right == null)

return false;

boolean cond1 = left.val == right.val;

boolean cond2 = Helper(left.left,right.right);

boolean cond3 = Helper(left.right, right.left);

return cond1 && cond2 && cond3;

}

}