蔚来Java后端9月6日机考笔试题

《面试题目》

1. 给定用花括号包裹、以逗号分隔且用 # 表示空节点的二叉树层序序列，如何求从根到叶子的最大实节点数？
2. 如何根据层序序列按队列重建二叉树，并正确处理空节点后不再登记子节点的规则？

《参考解析》

1. 去掉花括号后按逗号切分，把 # 转为空节点；从根开始用队列逐个取出真实节点，为其消费左右两个序列项，非空孩子入队。建树完成后再按层 BFS，每处理一层深度加一，队列为空时得到最大层深。
2. 采用迭代队列而不是递归，可避免输入退化成长链时栈溢出。时间复杂度为 O(n)，空间复杂度为 O(n)；示例 {2,#,8,#,9} 的右链深度为 3。