Как мне написать функцию в JavaScript, которая сравнивает два дерева, определенных TreeNodes a и b? - PullRequest
Новая
       44

Как мне написать функцию в JavaScript, которая сравнивает два дерева, определенных TreeNodes a и b?

0 голосов
/ 19 мая 2019

Я пытаюсь написать функцию 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;
}

Я ожидал, что вывод будет либо истинным, либо ложным, но вот что я получаю: 

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

Ответы [ 2 ]

1 голос
/ 28 мая 2019

Решение моего собственного вопроса после серьезного исследования показано в фрагменте ниже. 

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);
   }
}
0 голосов
/ 19 мая 2019

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

Самый простой подход - это 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)
}

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

...