Можно ли сравнить два бинарных дерева менее чем за O (n log n)?

Question

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

 public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode(int x) { val = x; }
 }

 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) && isSameTree(p.left, q.left) && 
      isSameTree(p.right, q.right))
        return true;
    else 
        return false;  
   }   
  }

Мой код занимает время O (n log n).

Как подойти к сокращению необходимого времени?

Answer 1

Текущее время выполнения вашего подхода на самом деле O(n), где n должно быть числом узлов дерева с меньшими (или, если они равны) узлами .

Кроме того, обратите внимание, что для сравнения всех значений структуры данных вам придется посетить все из них , и это время выполнения, которое вы можете достичь, а не сокращать дальше. В текущем случае, в худшем случае, вам придется посетить все узлы меньшего дерева и, следовательно, O(n).

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