Я смотрю на итеративное решение проверки, является ли дерево симметричным - PullRequest
Новая
       17

Я смотрю на итеративное решение проверки, является ли дерево симметричным

0 голосов
/ 09 апреля 2020

У меня есть следующий код: 

class TreeNode {
    constructor(val) {
        this.val = val
        this.left = this.right = null
    }
}

const isSymmetric = root => {
    if (!root) return true
    let stackP = []
    let stackQ = []
    let currentP = root
    let currentQ = root

    while ((currentP && currentQ) || (stackP.length && stackQ.length)) {

        while (currentP) {
            stackP.push(currentP)
            currentP = currentP.left
        }
        while (currentQ) {
            stackQ.push(currentQ)
            currentQ = currentQ.right
        }

        console.log(stackP, stackQ, 'after push')

        currentP = stackP.pop()
        currentQ = stackQ.pop()
        console.log(stackP, stackQ, 'after 1 iterative pop')

        if ((currentP.val !== currentQ.val) || (stackP.length !== stackQ.length)) return false
        console.log(currentP, currentQ, 'after if statement')

        // confused as to why we are setting it to the opposite here
        currentP = currentP.right
        currentQ = currentQ.left


        console.log(currentP, currentQ, 'after opp DECLARATION')
    }
    return true
}

//example 1
const tree1 = new TreeNode(1)
tree1.left = new TreeNode(2)
tree1.right = new TreeNode(2)

tree1.left.left = new TreeNode(3)
tree1.left.right = new TreeNode(4)

tree1.right.left = new TreeNode(4)
tree1.right.right = new TreeNode(3)

//example 2
const tree2 = new TreeNode(1)
tree2.left = new TreeNode(2)
tree2.right = new TreeNode(2)

tree2.left.right = new TreeNode(3)

tree2.right.right = new TreeNode(3)

console.log(isSymmetric(tree1));
console.log(isSymmetric(tree2));

Однако меня смущают две следующие строки: 

currentP = currentP.right
currentQ = currentQ.left

Я не уверен, почему это сделано. Я попытался следовать наряду с регистрацией консоли, но не в состоянии следовать. Я ожидал бы, что currentP сохранит себя в соответствии с исходным шаблоном, который установлен слева, но кажется, что после нажатия P и Q они теперь перемещаются вправо. Я не понимаю почему. Кто-нибудь может уточнить?

допустим, у нас есть следующее дерево 

   A 
  / \ 
 B   B 
/ \ / \ 
C D D C

отслеживание currentP и currentQ должны дать следующие значения A, B, C, C , null, B, D, null, A. Но когда мы добираемся до A, протекающего через логи c, кажется, что мы находимся в бесконечном l oop. Если я не отслеживаю это правильно. После того, как мы объявим currentP и currentQ как 'A', мы должны снова войти в циклы while, по сути, снова оттолкнув B и C, я что-то упустил?

1 Ответ

2 голосов
/ 09 апреля 2020

Учитывая это дерево: 

   A
  / \
 B   C
/ \ / \
D E F G

Сначала оно идет полностью налево (stackP = B, D), укладывая их, и вправо (stackQ = C, G). Затем сравните последние листья (D, G). Затем возьмите их братьев и сестер (E, F) и сравните - Это та часть, о которой вы говорили . Затем откройте их родителей (B, C) и сравните.

Вот программа с некоторой отладочной информацией, которая даст вам лучшее представление о том, что она делает: 

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

function serialize(arr) {
  return arr.map(e => e.val).join(",");
}

const isSymmetric = (root) => {
  if (!root) return true;
  let stackP = [];
  let stackQ = [];
  let currentP = root;
  let currentQ = root;

  while ((currentP && currentQ) || (stackP.length && stackQ.length)) {
    while (currentP) {
      stackP.push(currentP);
      console.log(`Pushing ${currentP.val} to sP=[${serialize(stackP)}]`)
      currentP = currentP.left;
    }
    while (currentQ) {
      stackQ.push(currentQ);
      console.log(`Pushing ${currentQ.val} to sQ=[${serialize(stackQ)}]`)
      currentQ = currentQ.right;
    }

    currentP = stackP.pop();
    currentQ = stackQ.pop();

    console.log(`Comparing cP=${currentP.val} cQ=${currentQ.val} sP=[${serialize(stackP)}] sQ=[${serialize(stackQ)}]`);

    if (currentP.val !== currentQ.val || stackP.length !== stackQ.length)
      return false;

    // confused as to why we are setting it to the opposite here
    currentP = currentP.right;
    currentQ = currentQ.left;

    console.log(`Looping   cP=${currentP ? currentP.val : "null"} cQ=${currentQ ? currentQ.val : "null"} sP=[${serialize(stackP)}] sQ=[${serialize(stackQ)}]`);
  }
  return true;
};

//example 1
const tree1 = new TreeNode(1)
tree1.left = new TreeNode(2)
tree1.right = new TreeNode(2)

tree1.left.left = new TreeNode(3)
tree1.left.right = new TreeNode(4)

tree1.right.left = new TreeNode(4)
tree1.right.right = new TreeNode(3)

//example 2
const tree2 = new TreeNode(1)
tree2.left = new TreeNode(2)
tree2.right = new TreeNode(2)

tree2.left.right = new TreeNode(3)

tree2.right.right = new TreeNode(3)

console.log(isSymmetric(tree1));
console.log(isSymmetric(tree2));
...