检查二叉树在JavaScript中是否对称
检查二叉树在JavaScript中是否对称
提问于 2017-04-28 09:30:08
给定一棵树，我应该检查它是否是对称的，或者是它自身的一面镜子。我遗漏了一个边缘案例，而且我永远也搞不清楚它是什么。我在CodeFights上得到的唯一错误是“超出输出限制”
Here's what the example tree looks like
这是主函数，isTreeSymmetric将其左分支分配给调用leftBranch函数的变量，将右分支分配给递归返回数组的rightBranch函数。
我之所以使用两个不同的函数，是因为它帮助我划分思路，因为在树的左半部分，我必须从右到左，反之亦然，这样我就不会在树洞中迷路。
然后，isTreeSymmetrical中的最后一个返回语句检查返回的类型值是否为数组，后跟一个三元数组，如果值不是数组，则检查左数组和右数组，或者检查变量lb和rb是否相等。
我已经在这上面工作了好久了！请帮帮忙。
function isTreeSymmetric(t) {
"use strict";
if(!t || ( (!t.left && !t.right) && t.value)) return true
if(!t.left || !t.right) return false
let left = t.left, right = t.right
let rb = rightBranch(right), lb = leftBranch(left)
console.log(`right branch values are ${rb} | left branch values are ${lb}`)
return Array.isArray( rb || lb ) ?
rb.every( (e, i) => e === lb[i]) :
lb === rb
}
//ON RIGHT BRANCH RETURN CHILDREN LEFT TO RIGHT
function rightBranch(n){
"use strict";
if(!n) return null
let value = n.value
if(!n.left && !n.right) return value
let left = n.left || null, right = n.right || null;
return [value].concat(
rightBranch(left),
rightBranch(right)
)
}
// ON LEFT BRANCH RETURN CHILDREN RIGHT TO LEFT
function leftBranch(n) {
"use strict";
if(!n) return null
let value = n.value
if(!n.left && !n.right) return value
let left = n.left || null, right = n.right || null;
return [value].concat(
leftBranch(right),
leftBranch(left))
}
let t = {
"value": 1,
"left": {
"value": 2,
"left": {
"value": 3,
"left": null,
"right": null
},
"right": {
"value": 4,
"left": null,
"right": null
}
},
"right": {
"value": 2,
"left": {
"value": 4,
"left": null,
"right": null
},
"right": {
"value": 3,
"left": null,
"right": null
}
}
}
console.log(isTreeSymmetric(t)) //true
回答 3
Stack Overflow用户
发布于 2017-07-26 19:38:05
实际上，您不需要检查节点或将其分组到数组中。就像你和@naomik做的那样，返回isTreeEqual(x.left，y.right) && isTreeEqual(x.right，y.left)。这将检查值和对称性(因为向右的分支需要对称，向左的分支需要对称，向右的分支需要对称，向左的分支需要对称)。
代码：
function isTreeSymmetric(t) {
if (!t){
return true
}
return isTreeEqual(t.left, t.right)
}
isTreeEqual = function(x, y) {
if (!x && !y){
return true
}
if (!x || !y){
return false
}
if (x.value === y.value){
return isTreeEqual(x.left, y.right) && isTreeEqual(x.right, y.left)
} else {
return false
}
} Stack Overflow用户
发布于 2017-04-28 10:14:04
我最好使用单个函数来遍历给定树的子节点。在上面的代码中，遍历的顺序是交换值，因此它无法检查对称树条件。检查下面的代码，让我知道它是否适合你。
function isTreeSymmetric(t) {
"use strict";
if(!t || ( (!t.left && !t.right) && t.value)) return true
if(!t.left || !t.right) return false
let left = t.left, right = t.right
let rb = traverseTree(right), lb = traverseTree(left)
return Array.isArray( rb || lb ) ?
rb.every( (e, i) => e === lb[i]) :
lb === rb
}
// ON traverseTree
function traverseTree(n) {
"use strict";
if(!n) return null
let value = n.value
if(!n.left && !n.right) return value
let left = n.left || null, right = n.right || null;
return [value].concat(
traverseTree(left),
traverseTree(right))
}
var tree;
tree = {
value: 1,
left: {
value: 2,
left: {
value: 3
},
right: {
value: 4
}
},
right: {
value: 2,
left: {
value: 3
},
right: {
value: 4
}
}
};
console.log(isTreeSymmetric(tree));
Stack Overflow用户
发布于 2018-10-20 04:36:26
这里有一个简单一点的版本，它只需要做一个级别的顺序遍历就可以解决JavaScript中的这个问题，希望它能有所帮助！
var isSymmetric = function(root) {
var levels = levelOrder(root)
for (var x = 1; x < levels.length; x++) {
var level = levels[x]
for (var i = 0, j = level.length-1; i < level.length; i++,j--) {
if (level[i] != level[j]) {
return false
}
}
}
return true
};
var levelOrder = function(node) {
if (node == null) { return []}
var discovered = [];
discovered.push(node)
var levels = levelOrderTraverse(discovered,[])
return levels
}
function levelOrderTraverse(discovered,elms) {
var level = []
for (var i = 0; i < discovered.length; i++) {
if (discovered[i] != null) {
level.push(discovered[i].val)
} else {
level.push("null")
}
}
elms.push(level);
var newlyDiscovered = [];
for (var i = 0; i < discovered.length; i++) {
if (discovered[i] != null) {
if (discovered[i].left != null) {
newlyDiscovered.push(discovered[i].left)
} else {
newlyDiscovered.push(null)
}
if (discovered[i].right != null) {
newlyDiscovered.push(discovered[i].right)
} else {
newlyDiscovered.push(null)
}
}
}
if (newlyDiscovered.length > 0) {
levelOrderTraverse(newlyDiscovered,elms)
}
return elms
}也可以在my github上找到
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/43670487
复制相关文章
相似问题
腾讯云开发者
