是否可以在小于O(n log n)的时间内比较两个二叉树？

Question

我编写了一个java例程来比较2个二叉树.我正在寻找在更短的时间内运行的更好的算法.

 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).

因此,任何其他方法都可以帮助您进行条件优化,您当前的解决方案具有无法进一步降低的最佳运行时间.