day139-LeetCode 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: But the following [1,2,2,null,3,null,3] is not
1
/ \
2 2
/ \ / \
3 4 4 3
把左子树反转就是右子树

分析

这题是反转二叉树和比较二叉树相同的结合

  1. 先反转二叉树
  2. 比较反转后的二叉树是否相等

题解


function isSymmetricTree (root) {
if (root === null || root.right === null || root.left === null) {
return true
}
// 反转
root.left = revertTree(root.right)
return isSameTree(root.left, root.right)
}

function revertTree(node) {
if(node == null || node.left == null && node.right == null) {
return node
}
let temp = revertTree(node.left)
node.left = revertTree(node.right)
node.right = temp
return node
}

function isSameTree (leftNode, rightNode) {
// 空节点,递归结束
if (leftNode === null || rightNode === null) {
return true
}
// 左右子树有一个为空
if (leftNode === null && rightNode !== null || leftNode !== null && rightNode === null) {
return false
}
// 判断非空节点是否相等
if (leftNode !== rightNode) {
return false
}
// 递归
return isSameTree(leftNode.right, rightNode.right) && isSameTree(leftNode.left, rightNode.left)
}
文章作者: lmislm
文章链接: http://lmislm.com/2019/05/31/2019-05-31/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 LMISLMのBlog