检查二叉树在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
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提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/43670487
复制相关文章
相似问题
腾讯云开发者
