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