102 lines
3.6 KiB
JavaScript
102 lines
3.6 KiB
JavaScript
/**
|
||
* Definition for a binary tree node.
|
||
* function TreeNode(val, left, right) {
|
||
* this.val = (val===undefined ? 0 : val)
|
||
* this.left = (left===undefined ? null : left)
|
||
* this.right = (right===undefined ? null : right)
|
||
* }
|
||
*/
|
||
/**
|
||
* @param {TreeNode} root
|
||
* @return {boolean}
|
||
*/
|
||
// const isSymmetric = function (root) {
|
||
// return f1(root.left, root.right);
|
||
// };
|
||
|
||
/*
|
||
递归：1.基础条件：如果两个树的根节点为空，则它们对称；如果一个为空而另一个不为空，则不对称；如果两个节点的值不相等，则不对称。
|
||
2.递归检查左右子树的对称性：左子树的左子树与右子树的右子树对称，左子树的右子树与右子树的左子树对称。
|
||
*/
|
||
|
||
function f1(left, right) {
|
||
// 如果左右两颗树的根节点都为空，则对称
|
||
if (!left && !right) return true;
|
||
// 上面判断排除了都为空的情况，所以至少有一颗树不为空，如果有的话，表明不对称
|
||
if (!left || !right) return false;
|
||
// 如果两个节点不为空，两个节点的值不相等返回false
|
||
if (left.val !== right.val) return false;
|
||
|
||
// 递归的对称检查，left.left和right.right, left.right和righ.left
|
||
|
||
return f1(left.left, right.right) && f1(left.right, right.left);
|
||
}
|
||
|
||
/*
|
||
使用bfs,使用两个队列，left和right，分别表示镜像每一层的左右节点，然后检查left从左到右存节点
|
||
right从右到左存节点，然后一一比较，如果都相当则表明这一层是对称的，继续检查下一层，如果每一层
|
||
都是对称的就表明整颗树都是对称的
|
||
*/
|
||
|
||
function f2(root) {
|
||
const queueL = [root.left]; // 遍历镜像左边的节点
|
||
const queueR = [root.right]; // 遍历镜像右边的节点
|
||
|
||
// 每一层的节点个数
|
||
let leaveSize = 1;
|
||
while (queueL.length > 0) {
|
||
console.log('lq: ', queueL);
|
||
console.log('rq: ', queueR);
|
||
|
||
// 判断左右节点
|
||
for (let i = 0; i < leaveSize; i++) {
|
||
// 取出对应节点比较
|
||
const leftSideNode = queueL.shift();
|
||
const rightSideNode = queueR.shift();
|
||
// 如果两个节点都为空，直接跳过本次循环,根本就没有子节点，无需做后面的操作
|
||
if (!leftSideNode && !rightSideNode) continue;
|
||
// 如果两个节点一个为空，直接返回false
|
||
if (!leftSideNode || !rightSideNode) return false;
|
||
// 左右两个节点值不相等
|
||
if (leftSideNode.val !== rightSideNode.val) return false;
|
||
// 将左侧和右侧的节点按照顺序压入栈中
|
||
queueL.push(leftSideNode.left);
|
||
queueL.push(leftSideNode.right);
|
||
queueR.push(rightSideNode.right);
|
||
queueR.push(rightSideNode.left);
|
||
}
|
||
leaveSize = queueL.length;
|
||
}
|
||
|
||
return true;
|
||
}
|
||
|
||
/*
|
||
dfs,只需一个循环依此检查即可，
|
||
*/
|
||
|
||
function f3(root) {
|
||
const stackL = [root.left]; // 遍历镜像左边的节点
|
||
const stackR = [root.right]; // 遍历镜像右边的节点
|
||
|
||
while (stackL.length > 0) {
|
||
// 拿出镜像左右两边的节点比较
|
||
const leftSideNode = stackL.pop();
|
||
const rightSideNode = stackR.pop();
|
||
|
||
// 如果两个值都为空就跳过
|
||
if (!leftSideNode && !rightSideNode) continue;
|
||
// 如果两个节点中有一个为null就返回false
|
||
if (!leftSideNode || !rightSideNode) return false;
|
||
// 如果两个节点都存在，但是值不相等返回false
|
||
if (leftSideNode.val !== rightSideNode.val) return false;
|
||
|
||
// 将左右节点压入栈中，leftSideNode.right->leftSideNode.left, rightSideNode.left->rightSideNode.right
|
||
stackL.push(leftSideNode.right);
|
||
stackL.push(leftSideNode.left);
|
||
stackR.push(rightSideNode.left);
|
||
stackR.push(rightSideNode.right);
|
||
}
|
||
return true;
|
||
}
|