本文共 1821 字，大约阅读时间需要 6 分钟。

为了解决这个问题，我们需要根据给定的中序和后序遍历序列，构建二叉树，并按照“zigzag”顺序输出节点的值。zigzag顺序是指从根开始，按层遍历，奇数层从左到右，偶数层从右到左。

方法思路

解决代码

import sysfrom collections import dequen = int(sys.stdin.readline())inorder = list(map(int, sys.stdin.readline().split()))postorder = list(map(int, sys.stdin.readline().split()))tree = {}root_id = 0def build(inL, inR, postL, postR):    global root_id    if inL > inR:        return    val = postorder[postR]    idx = inL    while idx <= inR and inorder[idx] != val:        idx += 1    l_size = idx - inL    current_id = root_id    tree[current_id] = {'left': None, 'right': None, 'value': val}    left_id = current_id + 1    build(inL, idx-1, postL, postL + l_size - 1, left_id)    right_id = current_id + 2    build(idx + 1, inR, postL + l_size, postR - 1, right_id)    root_id += 1build(1, n, 1, n)queue = deque()queue.append((0, 0))layer_nodes = []while queue:    node_id, depth = queue.popleft()    if len(layer_nodes) <= depth:        layer_nodes.append([])    layer_nodes[depth].append(node_id)    left = tree.get(node_id, {}).get('left', None)    if left is not None:        queue.append((left, depth + 1))    right = tree.get(node_id, {}).get('right', None)    if right is not None:        queue.append((right, depth + 1))result = []for depth in range(len(layer_nodes)):    nodes = layer_nodes[depth]    if depth % 2 == 0:        result.extend([tree[node]['value'] for node in nodes])    else:        result.extend([tree[node]['value'] for node in reversed(nodes)])print(' '.join(map(str, result)))

代码解释

这个方法确保了我们能够正确构建二叉树，并按照指定的zigzag顺序输出节点值。

转载地址：http://pxvfk.baihongyu.com/