9.8腾讯音乐笔试个人解法
个人解法，仅供参考，欢迎各位大佬友好讨论
第一题：给二叉树前序和中序遍历（节点值可能会重复），求所有可能的不同的树
个人觉得这个三题里面最难，思路参考********里的前序和中序遍历求后序遍历，同样都是递归分治
function lop(pre, ord) {
if (!pre.length || !ord.length) return [null]
let arr = []
for (let i = 0; i < pre.length; i++) {
if (pre[0] == ord[i]) {
let left = lop(pre.slice(1, 1 + i), ord.slice(0, i))
let right = lop(pre.slice(i + 1), ord.slice(i + 1))
if (left.length && right.length) {
for (let l of left) {
for (let r of right) {
arr.push(new TreeNode(pre[0], l, r))
}
}
}
}
}
return arr
}
问题转换：本质上是求左右两颗子树数量最大的那个，因为权值最小为1，且可以重复，故两颗子树要权值最小值为两颗子树数量最大的那个，dfs两行结束（我这的代码可能有问题，思路没错就行）
function dfs(root) {
if (!root) return 0
return 1 + 2 * Math.max(dfs(root.left), dfs(root.right))
} 模拟题，字符串限定了只有小写字母，就很easy了，我们这里不使用哈希表，用一个数组来存放字符的次数，然后模拟就可以了
function mo(str) {
let arr = new Array(26).fill(0)
let count = 0
for (let s of str) {
arr[s.charCodeAt() - 'a'.charCodeAt()]++
}
while (arr.some(val => val > 1)) {
let index = arr.findIndex(val => val > 1)//这里可以优化,但只有26其实无所谓
arr[index] -= 2
let last = arr.indexOf(Math.min(...arr))//这里也是，可以用堆排序
arr[last]++
count++
}
return count
} 
self.ans = 0 def traverse(self,root): if root == None: return 0 left = self.traverse(self, root.left) right = self.traverse(self, root.right) if left == right: self.ans += 1 else: self.ans =2* max(left,right) return left + right + 1 return self.ans
查看11道真题和解析
