101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1   / \  2   2 / \ / \3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

1   / \  2   2   \   \    3   3

Follow up: Solve it both recursively and iteratively.

Analyze

/** * Definition for a binary tree node. * function TreeNode(val) { *     this.val = val; *     this.left = this.right = null; * } *//** * @param {TreeNode} root * @return {boolean} */var isSymmetric = function (root) {  if (root === null) {    return true  }  return isMirror(root.left, root.right)};
function isMirror(leftNode, rightNode) {  if (leftNode === null && rightNode === null) {    return true  }
if (leftNode === null || rightNode === null) {    return false  }
if (leftNode.val === rightNode.val) {    return isMirror(leftNode.left, rightNode.right) && isMirror(leftNode.right, rightNode.left)  } else {    return false  }}

1      /   \    2       2   / \     / \  3   4   4   3 / \ / \ / \ / \5  6 7 8 8 7 6  5

• 第一步: stack = [2, 2];
• 第二步: 取出 [2, 2], 推入 [3, 3, 4, 4];
• 第三步: 取出 [4, 4], 推入 [7, 7, 8, 8];
• 第四步: 取出 [8, 8];
• 第五步: 取出 [7, 7], 取出 [3, 3];
• 第六步: 推入 [5, 5, 6, 6];
• 第七步: 取出 [6, 6];
• 第八步: 取出 [5, 5];
/** * Definition for a binary tree node. * function TreeNode(val) { *     this.val = val; *     this.left = this.right = null; * } *//** * @param {TreeNode} root * @return {boolean} */var isSymmetric = function (root) {  if (!root) return true  if (!root.left && !root.right) return true  if (root.left && root.right && root.left.val !== root.right.val) return false
const stack = []
stack.push(root.right)  stack.push(root.left)
while (stack.length > 0) {    const popItemLeft = stack.pop()    const popItemRight = stack.pop()
if (!popItemLeft && !popItemRight) continue    if (!popItemLeft || !popItemRight || popItemLeft.val !== popItemRight.val) return false
stack.push(popItemRight.right, popItemLeft.left, popItemRight.left, popItemLeft.right)  }
return true};