100. Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

100. Одинаковые деревья

Заданы два бинарных дерева. Напишите функцию, которая проверит, одинаковы ли они.

Два бинарных дерева считаются одинаковыми, если они идентичны по структуре, а соответствующие вершины имеют одинаковые значения.

// C++

class Solution {

public:

bool isSameTree(TreeNode *p, TreeNode *q) {

}

};

// Java

public class Solution {

public boolean isSameTree(TreeNode p, TreeNode q) {

}

};

РЕШЕНИЕ

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

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

Если p = q = NULL, то деревья идентичны.

Если один из указателей p или q равен NULL, а второй не равен NULL, то деревья не идентичны.

Если p -> val и q -> val не равны между собой, то деревья не идентичны.

Если p -> val и q -> val равны, то рекурсивно проверяем идентичность их левых и правых поддеревьев.

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

class Solution

{

public:

bool isSameTree(TreeNode *p, TreeNode *q)

{

if(p == NULL && q == NULL)

return true;

else if(p == NULL || q == NULL)

return false;

if(p->val == q->val)

{

bool left = isSameTree(p->left, q->left);

bool right = isSameTree(p->right,q->right);

return left && right;

}

return false;

}

};

Java реализация

public class Solution

{

public boolean isSameTree(TreeNode p, TreeNode q)

{

if(p == null && q == null)

return true;

else if(p == null || q == null)

return false;

if(p.val == q.val)

{

boolean left = isSameTree(p.left, q.left);

boolean right = isSameTree(p.right,q.right);

return left && right;

}

return false;

}

}