Задача с собеседования Яндекс

Задача
Даны корни двух бинарных деревьев p и q Нужно проверить совпадают ли деревья Два дерева считаются одинаковыми если они структурно идентичны и значения соответствующих узлов равны

Чат алгоритмистов

Решение
Идем синхронно по обоим деревьям, если оба указателя пустые поддеревья совпадают, если пуст только один деревья различаются, затем сравниваем значения текущих узлов и рекурсивно проверяем левое и правое поддерево если все проверки проходят деревья одинаковые
Время O(n) где n число узлов каждый узел посещаем не более одного раза
Память O(h) для стека рекурсии где h высота дерева в худшем случае O(n) в сбалансированном O(log n)

Код
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) {
return true;
}
if (!p || !q) {
return false;
}
return p->val == q->val
&& isSameTree(p->left, q->left)
&& isSameTree(p->right, q->right);
}
};


@algoses