Created
February 13, 2019 15:22
-
-
Save monsterooo/0c7125d5985eea83b08f4d7d1cdecf69 to your computer and use it in GitHub Desktop.
算法练习-判断二叉树是否对称
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
对称二叉树树 | |
1 | |
/ \ | |
2 2 | |
/ \ / \ | |
4 8 8 4 | |
*/ | |
// 对称二叉树树 | |
var symmetricTree = { | |
val: 1, | |
left: { | |
val: 2, | |
left: { | |
val: 4, | |
}, | |
right: { | |
val: 8 | |
} | |
}, | |
right: { | |
val: 2, | |
left: { | |
val: 8, | |
}, | |
right: { | |
val: 4, | |
} | |
} | |
} | |
/* | |
非对称二叉树树 | |
1 | |
/ \ | |
2 2 | |
/ \ / | |
4 8 8 | |
*/ | |
// 非对称二叉树树 | |
var notSymmetricTree = { | |
val: 1, | |
left: { | |
val: 2, | |
left: { | |
val: 4, | |
}, | |
right: { | |
val: 8 | |
} | |
}, | |
right: { | |
val: 2, | |
left: { | |
val: 8, | |
}, | |
} | |
} | |
// 递归实现 | |
function isSymmetricTreeRecursive(root) { | |
// 树为空返回true | |
if (!root) return true; | |
// 返回他们的对称性 | |
return isSymmetric(root.left, root.right); | |
} | |
// 迭代实现 | |
function isSymmetricTreeIterative(root) { | |
if (!root) return true; | |
var stack = []; // 定义一个辅助栈 | |
// 根节点的左右子树入栈 | |
stack.unshift(root.left); | |
stack.unshift(root.right); | |
// 栈不为空一直执行操作 | |
while (stack.length) { | |
var s = stack.shift(), t = stack.shift(); | |
if (!s && !t) continue; // 都为空继续执行操作 | |
if (!s || !t) return false; // 一个为空一个不为空肯定不对称 | |
if (s.val != t.val) return false; // 如果两个节点值不同,则不对称 | |
stack.unshift(s.left); // 左左子树 对 右右子树 | |
stack.unshift(t.right); | |
stack.unshift(s.right); // 左右子数 对 右左子树 | |
stack.unshift(t.left); | |
} | |
return true; | |
} | |
// 对比两颗二叉树是否对称 | |
function isSymmetric(s, t) { | |
// s t 树都存在时判断 | |
if (s && t) { | |
return s.val === t.val && // 当前节点值是否相等 | |
// 左节点的左子树 和 右节点的右子树是否相等 | |
// 左节点的右子树 和 右节点的左子树是否相等 | |
isSymmetric(s.left, t.right) && isSymmetric(s.right, t.left); | |
} else { | |
// s t 都为空返回 true. 为了判断最底层节点都没有的情况 | |
return !s && !t; | |
} | |
} | |
console.log('递归判断对称二叉树 > ', isSymmetricTreeRecursive(symmetricTree)); | |
console.log('递归判断非对称二叉树 > ', isSymmetricTreeRecursive(notSymmetricTree)); | |
console.log('迭代判断对称二叉树 > ', isSymmetricTreeIterative(symmetricTree)); | |
console.log('迭代判断非对称二叉树 > ', isSymmetricTreeIterative(notSymmetricTree)); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment