То же бинарное дерево

Вопрос

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

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

Вы можете потренироваться на leetcode, прежде чем читать решение

Решение

Разобьём вопрос на объективные части

Первая идея, когда у нас есть дерево, — это рекурсия, так как мы никогда не знаем их глубины.

У нас есть 2 шага здесь.

1. Проверьте, совпадают ли корни (оба нулевые или оба имеют одинаковое значение)

2. Если это не так, верните false

3. если корень тот же, мы проверяем, совпадают ли соответствующие левый и правый

Код на Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        boolean ans =true;
        if(p==null&&q==null){
            return ans;
        }
        if(p==null){
            return false;
        }
        if(q==null){
            return false;
        }
        return (p.val==q.val)&&isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

Оценка

Космическая сложность: O(h)

Временная сложность: O(n)