MetaApp开发面试题目【LeetCode】1.二叉树，第一行从左到右第二行从右到左2.链表翻转：

87 阅读 0 评论 58 点赞

我是靠谱客的博主负责棒球，这篇文章主要介绍MetaApp开发面试题目【LeetCode】1.二叉树，第一行从左到右第二行从右到左2.链表翻转：，现在分享给大家，希望可以做个参考。

1.二叉树，第一行从左到右第二行从右到左

leetcode:力扣

1.特例处理：当树的根节点为空，则直接返回空列表 [] ；
2.初始化：打印结果空列表 res ，包含根节点的双端队列 deque ；
3.BFS 循环：当 deque 为空时跳出；
        新建列表 tmp ，用于临时存储当前层打印结果；
        当前层打印循环：循环次数为当前层节点数（即 deque 长度）；
        出队：队首元素出队，记为 node；
        打印：若为奇数层，将 node.val 添加至 tmp 尾部；否则，添加至 tmp 头部；
        添加子节点：若 node 的左（右）子节点不为空，则加入 deque ；
        将当前层结果 tmp 转化为 list 并添加入 res ；
        返回值：返回打印结果列表 res 即可；

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
res, deque = [], collections.deque([root])
while deque:
tmp = collections.deque()
for _ in range(len(deque)):
node = deque.popleft()
if len(res) % 2: tmp.appendleft(node.val) # 偶数层 -> 队列头部
else: tmp.append(node.val) # 奇数层 -> 队列尾部
if node.left: deque.append(node.left)
if node.right: deque.append(node.right)
res.append(list(tmp))
return res

2.链表翻转：

LeetCode：力扣

双指针：考虑遍历链表，并在访问各节点时修改 next 引用指向

复制代码

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre, cur = None, head
while cur:
tmp = cur.next
#暂存下一个节点
cur.next = pre
# 改变cur的next指向
pre = cur # pre 指向cur的位置
cur = tmp # cur指向下一个节点
return pre