javascript - 我正在寻找检查树是否对称的迭代解决方案

Question

我有以下代码:

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时从逻辑上看，我们似乎处于无限循环中。除非我没有正确跟踪它。在我们将 currentP 和 currentQ 声明为“A”之后，我们应该再次进入 while 循环，本质上是再次将 B 和 C 推回去，我是否错过了什么？

Answer 1

给定这棵树:

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

首先，它一直向左(stackP = B，D)堆叠它们，然后向右(stackQ = C，G)。然后比较最后的叶子(D，G)。然后拿他们的 sibling (E，F)进行比较 - 这就是您正在谈论的部分。然后弹出他们的 parent (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));