gpt4 book ai didi

python - Zigzag级序遍历

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:46:24 25 4
gpt4 key购买 nike

I am trying to do the zigzag level order traversal of a binary tree's nodes values (ie, from left to right, then right to left for the next level and alternate between) on https://www.interviewbit.com/problems/zigzag-level-order-traversal-bt/ But the compiler gives time limit exceeded error. How can I resolve it?

# Definition for a  binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
# @param A : root node of tree
# @return a list of list of integers
def zigzagLevelOrder(self, A):
st_crt_lvl =[A]
st_nxt_lvl =[]
ans_list = []

while st_crt_lvl:
u = st_crt_lvl.pop(0)
ans_list.append(u.val)
if u.left:
st_nxt_lvl.append(u.left)
if u.right:
st_nxt_lvl.append(u.right)
while st_nxt_lvl:
u = st_nxt_lvl.pop()
ans_list.append(u.val)

if u.right:
st_crt_lvl.append(u.right)
if u.left:
st_crt_lvl.append(u.left)


return ans_list

最佳答案

您可以从代码中消除多个内部 while 循环,方法是使队列 st_nxt_lvl 成为临时队列并将此临时队列的内容复制到当前队列 st_crt_lvl 最后处理二叉树的每一层。

这可以通过只保留一个队列(没有任何临时存储)和标准 bfs 算法的级别顺序遍历来实现,但是由于我们希望在每个级别都进行锯齿形顺序遍历,因此更多有一个临时队列很优雅,这样临时队列只保留下一级元素,当当前级别元素处理完成时,当前队列指向下一级。

对您的代码进行一些修改,以及示例树:

def zigzagLevelOrder(A):

st_crt_lvl = [A] # initialize
ans_list = []

level = 0
while st_crt_lvl: # check if all levels are processed
st_nxt_lvl =[] # temporary queue to hold the next level elements
tmp = [] # temporary storage to append to the ans_list
while st_crt_lvl:
u = st_crt_lvl.pop(0)
tmp.append(u.val)
if u.left:
st_nxt_lvl.append(u.left)
if u.right:
st_nxt_lvl.append(u.right)
if (len(tmp) > 0): # if tmp is not empty
if level % 2 == 1: # ensure zig-zag level order traversal
tmp = tmp[::-1]
ans_list.append(tmp)
st_crt_lvl = st_nxt_lvl # copy the temporary queue to the current queue
level += 1

return ans_list


class BinaryTree:
def __init__(self, left, right, data):
self.left = left
self.right = right
self.val = data

A = BinaryTree(None, None, 3)
A.left = BinaryTree(None, None, 9)
A.right = BinaryTree(None, None, 20)
A.left.left = BinaryTree(None, None, 1)
A.left.right = BinaryTree(None, None, 2)
A.right.left = BinaryTree(None, None, 15)
A.right.right = BinaryTree(None, None, 7)
zigzagLevelOrder(A)
# [[3], [20, 9], [1, 2, 15, 7]]

关于python - Zigzag级序遍历,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51889381/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com