Имея два непустых бинарных дерева s и t, проверьте, имеет ли дерево t точно такую ​​же структуру и значения узлов с поддеревом >с. Поддерево s — это дерево, состоящее из узла в s и всех потомков этого узла. Дерево s также можно рассматривать как собственное поддерево.

Пример 1:
Даны деревья:

     3
    / \
   14  5
  / \
 11   2

Данное дерево t:

   14 
  /  \
 11   2

Верните true, так как t имеет ту же структуру и значения узлов, что и поддерево s.

Пример 2:
Даны деревья:

     3
    / \
   8   5
  / \
 1   2
    /
   0

Данное дерево t:

   8
  / \
 1   2

Вернуть false.

Решение

Подход № 1 с использованием обхода предварительного заказа

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    HashSet < String > trees = new HashSet < > ();
    public boolean isSubtree(TreeNode s, TreeNode t) {
        String tree1 = preorder(s, true);
        String tree2 = preorder(t, true);
        return tree1.indexOf(tree2) >= 0;
    }
    public String preorder(TreeNode t, boolean left) {
        if (t == null) {
            if (left)
                return "lnull";
            else
                return "rnull";
        }
        return "#"+t.val + " " +preorder(t.left, true)+" " +preorder(t.right, false);
    }
}

Анализ сложности

  • Временная сложность: O(m²+n²+m*n)O(m2+n2+m *n). Всего пройдено n узлов дерева ss и mm узлов дерева tt. Предполагая, что конкатенация строк занимает O(k)O(k) времени для строк длины kk, а indexOf занимает O(m*n)O(m∗n).
  • Пространственная сложность: O(max(m,n))O(max(m,n)). Глубина дерева рекурсии может достигать n для дерева tt и mm для дерева ss в худшем случае.

Подход № 2 путем сравнения узлов

Алгоритм

Вместо того, чтобы создавать неупорядоченный обход, мы можем рассматривать каждый узел данного дерева tt как корень, рассматривать его как поддерево и сравнивать соответствующее поддерево с заданным поддеревом ss для равенства. Для проверки равенства мы можем сравнить все узлы двух поддеревьев.

Для этого мы используем функцию dfs(s,t), которая проходит по заданному дереву s и рассматривает каждый узел как корень рассматриваемого в данный момент поддерева. Он также проверяет два рассматриваемых в настоящее время поддерева на их равенство. Чтобы проверить равенство двух поддеревьев, мы используем isEquals(x,y) функцию, которая принимает xx и yy, являющиеся корнями двух поддеревьев, в сравниваться как входные данные и возвращает True или False в зависимости от того, равны они или нет. Он сравнивает все узлы двух поддеревьев на равенство. Во-первых, он проверяет, равны ли корни двух деревьев, а затем рекурсивно вызывает себя для левого поддерева и правого поддерева.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        return dfs(s, t);
    }
    
    private boolean dfs(TreeNode s, TreeNode t) {
        
        return s!=null && (isEquals(s,t) || dfs(s.left, t) || dfs(s.right, t));
    }
    
    private boolean isEquals(TreeNode s, TreeNode t) {
        if(s == null && t == null) {
            return true;
        } else if(s == null || t == null) {
            return false;
        }
        
        return s.val == t.val && isEquals(s.left, t.left) && isEquals(s.right, t.right);
    }
}

Анализ сложности

  • Временная сложность: O(m*n)O(m∗n). В худшем случае (перекошенное дерево) функция traverse занимает O(m*n)O(m∗n) времени.
  • Пространственная сложность: O(n)O(n). Глубина дерева рекурсии может достигать n. n – количество узлов в ss.