Вопрос

Имея корни двух бинарных деревьев p и q, напишите функцию, проверяющую, совпадают ли они или нет.

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

Пример 1:

Input: p = [1,2,3], q = [1,2,3]
Output: true

Пример 2:

Input: p = [1,2], q = [1,null,2]
Output: false

Пример 3:

Input: p = [1,2,1], q = [1,1,2]
Output: false

Ограничения:

  • Количество узлов в обоих деревьях находится в диапазоне [0, 100].
  • -104 <= Node.val <= 104

Java-решение

O(n)
Где n — количество узлов в дереве
Ps: в случае Java n будет числом узлов в дереве, но дерево, в котором меньше узлов. Потому что в Java есть оценка короткого замыкания.

Код

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null)
return true;
if(p == null || q == null)
return false;
if(p.val != q.val)
return false;
return (isSameTree(p.left, q.left) && isSameTree(p.right, q.right));
}
}
view raw 8.java hosted with ❤ by GitHub