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

Question

我正在尝试编写一个 JavaScript 函数来比较由 TreeNodes a 和 b 和 returns 定义的两个二叉树如果它们在结构和值上相等并且否则为假。

例如example of comparing both values and structure of two binary trees

给出以下 class：

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

一种 quick-and-dirty 方法可以是为树定义规范序列化，然后比较它们。

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

实现自定义 toJSON 方法

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就变得微不足道了。

编辑：一旦您在 TreeNode 上定义了自定义 toJSON 方法，那么 binaryTreeCompare 将变为：

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

但是，您报告的错误信息与您的算法无关。很难确定问题出在哪里，因为错误消息引用了示例代码中未出现的内容。我怀疑您的真实代码与您发布的代码在某种程度上对问题至关重要。

Answer 2

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

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);
   }
}

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

How do i write a function in JavaScript that compares two trees defined by TreeNodes a and b?

javascript

algorithm

binary-tree

binary-search-tree

data-structures