分析几道大厂算法题
很多大厂第一面都很有可能会是笔试题，题目大多包括JS的基础题和算法题，今天小编将分享几道算法，希望对你们的面试有所帮助。
01
问题
描述：二叉树的数据结构如下，需要将二叉树各节点左右翻转。
var node1 = {
value: 1,
left: {
value: 2,
left: {
value: 4
},
right: {
value: 5
}
},
right: {
value: 3,
left: {
value: 6
},
right: {
value: 7
}
}
}
参考答案
function reverse(node) {
if (node != null) {
let temp = node.left;
node.left = node.right;
node.right = temp;
reverse(node.left);
reverse(node.right);
}
}
02
问题
描述：实现函数接收任意二叉树，求二叉树所有根到叶子路径组成的数字之和。
class TreeNode {
constructor () {
this.value = undefined;
this.left = null;
this.right = null;
}
}
参考答案
function getPathSum(root) {
let total = 0
function next(node) {
if (node != undefined) {
total += node.value
next(node.left)
node(node.right)
}
}
next(node)
return total
}
03
问题
描述：一层二叉树定义如下，路径是1->2,1->3，按照要求实现 getPathSum(node) 方法返回7=(1+2)+(1+3)
class TreeNode {
constructor () {
this.value = undefined;
this.left = null;
this.right = null;
}
}
const node = new TreeNode()
node.value = 1;
node.left = new TreeNode()
node.left.value = 2
node.right = new TreeNode();
node.right.value = 3
参考答案
function getPathSum(node) {
let leftNumber = []
let rightNumber = []
let total = 0
function calculateLeft(node) {
if (node != undefined) {
leftNumber.push(node.value)
total += node.value
calculateLeft(node.left)
}
}
function calculateRight(node) {
if (node != undefined) {
rightNumber.push(node.value)
total += node.value
calculateRight(node.right)
}
}
calculateLeft(node)
calculateRight(node)
let result = `
${total}=
(${leftNumber.join('+')})+
(${rightNumber.join('+')})
`
return result
}
getPathSum(node) // 7=(1+2)+(1+3)
04
问题
描述：参考下面代码，按照要求实现 sum 函数，并且考虑性能和执行效率。
(async function () {
let a = await sum(1, 2, 3, 4)
let b = await sum(1, 2, 3, 4)
console.log([a, b])
})()
function addAsync(a, b, callback) {
setTimeout(() => {
callback(null, a + b)
}, 1000);
}
参考答案
function handler(a, b) {
return new Promise((resolve, reject) => {
addAsync(a, b, (err, res) => {
if (err) {
reject(err)
} else {
resolve(res)
}
})
})
}
async function sum(...args) {
async function next(args) {
if (args.length === 1) {
return args[0]
} else {
// 判断是奇数还是偶数
if (args.length % 2 === 0) {
// 偶数
let list = []
for (let i = 0; i < args.length; i++) {
let a = args[i++]
let b = args[i]
list.push(handler(a, b))
}
let result = await Promise.all(list)
let end = await next(result)
return end
} else {
// 奇数
let last = args.pop()
let list = []
for (let i = 0; i < args.length; i++) {
let a = args[i++]
let b = args[i]
list.push(handler(a, b))
}
let result = await Promise.all(list)
let end = await next(result.concat(last))
return end
}
}
}
let total = await next(args)
return total
}
错误写法
function handler(a, b) {
return new Promise((resolve, reject) => {
addAsync(a, b, (err, res) => {
if (err) {
reject(err)
} else {
resolve(res)
}
})
})
}
async function sum(...args) {
let total = 0
for (let i = 0; i < args.length; i++) {
total = await handler(total, args[i])
}
return total
}
有三个是关于二叉树的问题，有一个是性能优化相关的问题，想了解更多关于二叉树基础的知识，可以参考我这篇文章：《二叉树》
End