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