题目描述
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
链接：https://leetcode-cn.com/problems/symmetric-tree
我的AC代码
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
let arrIsSymmetric = function (arr) {
for(let i = 0, j = arr.length -1; i < j; i++, j--) {
if (arr[i] !== arr[j]) {
return false;
}
}
return true;
}
方法四：递归，使用二维数组存放遍历结果，然后判断每一层的遍历数组是否对称
/* var isSymmetric = function(root) {
if(!root){return true;}
let res = [];
var traverse = function(root, level) {
if(res[level]) {
res[level].push(root ? root.val : null);
}
else {
res[level] = [root ? root.val : null];
}
if (root) {
traverse(root.left, level + 1);
traverse(root.right, level + 1);
}
}
traverse(root, 0);
for (let i = 0; i < res.length; i++) {
if (!arrIsSymmetric(res[i])) {
return false
}
}
return true;
}; */
// 方法三：迭代，判断每一层的遍历数组是否对称，不同层使用特殊字符进行分割
/* var isSymmetric = function(root) {
if (!root) {
return true;
}
let arr = [root, 'd'];
let currentLevelArr = [];
while(arr.length) {
let ele = arr.shift();
if (arr.length === 0 && ele === 'd') {
break;
}
if (ele === 'd') {
arr.push('d');
if (!arrIsSymmetric(currentLevelArr)) {
return false;
}
currentLevelArr = [];
continue;
}
else {
currentLevelArr.push(ele ? ele.val : null);
if (ele) {
arr.push(ele.left);
arr.push(ele.right);
}
}
}
return true;
} */
// 方法二：递归，判断对称位置节点的左子树与右子树是否对称
/* var isMirror = function(a, b) {
if (a === null && b=== null) {
return true;
}
if (a === null || b === null) {
return false;
}
if (a.val === b.val) {
return isMirror(a.left, b.right) && isMirror(b.left, a.right)
}
else {
return false;
}
}
var isSymmetric = function(root) {
return isMirror(root, root);
} */
// 方法一：迭代，从左到右遍历与从右遍历的的顺序应该是一致的
var isSymmetric = function(root) {
let q = [root];
let p = [root];
while(q.length) {
let qEle = q.shift();
let pEle = p.shift();
if (qEle === null && pEle === null) {
continue;
}
if (qEle === null || pEle === null) {
return false;
}
if (pEle.val !== qEle.val) {
return false;
}
q.push(qEle.left);
q.push(qEle.right);
p.push(pEle.right);
p.push(pEle.left);
}
return true;
}
题解
方法1: 迭代，从左到右遍历与从右遍历的的顺序应该是一致的
使用队列的方法，用两个队列，一个从左到右遍历，一个从右到左遍历，如果二叉树的平衡的话，那么队列中的元素应该是一致的。时间复杂度O(n),空间 复杂度O(n)
方法2:递归，判断对称位置节点的左子树与右子树是否对称
使用递归的方法，判断对应位置的节点值是否相等，不相等则不对称，相等则判断两个位置的左子树和右子树是否对称。 时间复杂度O(n),空间复杂度O(n)
