我如何在 JavaScript 中编写一个函数来比较由 TreeNodes a 和 b 定义的两棵树？

Question

我正在尝试编写一个 JavaScript 函数，该函数比较由

TreeNode

s a 和 b 定义的两个二叉树，如果它们在结构和值上相等则返回 true，否则返回 false。

例如比较两个二叉树的值和结构的示例

给出以下课程：

class TreeNode {
  constructor(data, left=null, right=null) {
    this.data = data;
    this.left = left;
    this.right = right;
  }
}

这是我迄今为止尝试编写的比较 TreeNode a 和 b 的代码。

const binaryTreeCompare = (a, b) => {
  if(a==null && b==null){
    return true;
  }else if(a!=null && b!=null){
    return(
      a.data == b.data && binaryTreeCompare(a.left, b.left) && binaryTreeCompare(a.right, b.right)
    );
  }
    else return false;
}

我期望输出为 true 或 false，但这就是我得到的：

ReferenceError: compare is not defined
    at Context.it (test.js:116:16)

Answer 1

经过认真研究后我自己的问题的解决方案如下面的代码片段所示。

function compare(a, b){
  if (!a && !b) {
      return true;
   } else if (!a || !b) {
      return false;
   } else {
      return a.val === b.val && compare(a.left, b.left) && compare(a.right, b.right);
   }
}

Answer 2

一种快速而肮脏的方法可能是为树定义规范序列化，然后比较它们。

最简单的方法是对每棵树进行 JSON.stringify。您需要为

toJSON

实现自定义

TreeNode

方法。

class TreeNode {
  constructor(data, left=null, right=null) {
    this.data = data;
    this.left = left;
    this.right = right;
  }

  toJSON() {
    return JSON.stringify({ data: this.data, left: this.left, right: this.right });
  }
}

那么，

binaryTreeCompare

就变得微不足道了。

编辑：一旦您在

toJSON

上定义了自定义

TreeNode

方法，那么

binaryTreeCompare

就变成了这样：

function binaryTreeCompare(a, b) {
    return JSON.stringify(a) === JSON.stringify(b)
}

---

但是，您报告的错误信息与您的算法无关。很难确定问题是什么，因为错误消息引用了示例代码中未出现的内容。我怀疑您的真实代码与您发布的代码有所不同，这对问题至关重要。

Answer 3

TreeObjectDiff 是一个小型、快速且零依赖的实用程序，用于比较和识别树结构对象之间的差异。