22275: 二叉搜索树的遍历

http://cs101.openjudge.cn/practice/22275/

给出一棵二叉搜索树的前序遍历，求它的后序遍历

输入

第一行一个正整数n（n<=2000）表示这棵二叉搜索树的结点个数第二行n个正整数，表示这棵二叉搜索树的前序遍历保证第二行的n个正整数中，1~n的每个值刚好出现一次

输出

一行n个正整数，表示这棵二叉搜索树的后序遍历

样例输入

5
4 2 1 3 5

样例输出

1 3 2 5 4

提示

树的形状为 4
/ \ 2 5 / \ 1 3

python

class Node:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_bst(preorder):
    if not preorder:
        return None
    root = Node(preorder[0])
    i = 1
    while i < len(preorder) and preorder[i] < root.val:
        i += 1
    root.left = build_bst(preorder[1:i])
    root.right = build_bst(preorder[i:])
    return root

def post_order(root):
    if not root:
        return []
    # 先左子树，后右子树，最后根节点
    return post_order(root.left) + post_order(root.right) + [root.val]


# Read input
n = int(input())
preorder = list(map(int, input().split()))

# Build BST and get postorder traversal
root = build_bst(preorder)
res = post_order(root)
print(' '.join(map(str, res)))

python

"""
王昊 光华管理学院。思路：
建树思路：数组第一个元素是根节点，紧跟着是小于根节点值的节点，在根节点左侧，直至遇到大于根节点值的节点，
后续节点都在根节点右侧，按照这个思路递归即可
"""
class Node():
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def buildTree(preorder):
    if len(preorder) == 0:
        return None

    node = Node(preorder[0])

    idx = len(preorder)
    for i in range(1, len(preorder)):
        if preorder[i] > preorder[0]:
            idx = i
            break
    node.left = buildTree(preorder[1:idx])
    node.right = buildTree(preorder[idx:])

    return node


def postorder(node):
    if node is None:
        return []
    output = []
    output.extend(postorder(node.left))
    output.extend(postorder(node.right))
    output.append(str(node.val))

    return output


n = int(input())
preorder = list(map(int, input().split()))
print(' '.join(postorder(buildTree(preorder))))

python

# 管骏杰 生命科学学院
# 中序遍历就是顺序排列，进而通过上次作业的思路根据前序中序推出后序
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def build(preorder, inorder):
    if not preorder or not inorder:
        return None
    root_val = preorder[0]
    root = Node(root_val)
    root_index = inorder.index(root_val)
    root.left = build(preorder[1:root_index + 1], inorder[:root_index])
    root.right = build(preorder[root_index + 1:], inorder[root_index + 1:])
    return root


def postorder(root):
    if not root:
        return []
    if root.left is None and root.right is None:
        return [root.val]
    result = []
    result += postorder(root.left)
    result += postorder(root.right)
    result += [root.val]
    return result


input()
preorder = list(map(int, input().split()))
inorder = sorted(preorder)
root = build(preorder, inorder)
result = postorder(root)
print(' '.join(map(str, result)))

python

def post_order(pre_order):
    if not pre_order:
        return []
    root = pre_order[0]
    left_subtree = [x for x in pre_order if x < root]
    right_subtree = [x for x in pre_order if x > root]
    return post_order(left_subtree) + post_order(right_subtree) + [root]

n = int(input())
pre_order = list(map(int, input().split()))
print(' '.join(map(str, post_order(pre_order))))

python

class Treenode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# 构建二叉搜索树
def buildtree(p):
    n = len(p)
    stack = []
    root = Treenode(p[0])
    stack.append(root)

    for i in range(1, n):
        cur = Treenode(p[i])
        if p[i] < stack[-1].val:
            stack[-1].left = cur
            stack.append(cur)
        else:
            pre = None
            while stack and p[i] > stack[-1].val:
                pre = stack.pop()
            pre.right = cur
            stack.append(cur)

    return root

# 后序遍历
def hou(root):
    if not root:
        return []
    return hou(root.left) + hou(root.right) + [root.val]

# 输入处理
n = int(input())
p = list(map(int, input().split()))

# 构建BST并获取后序遍历结果
root = buildtree(p)
ans = hou(root)

# 输出结果
print(' '.join(map(str, ans)))

【龚正宁 2025fall-cs201 工学院】思路：灵机一动发现可以先提取根节点然后找到左右两部分，接着分治（因为左<根<右的性质即使在子树也成立），所以直接递归秒了。犯脑残了，定义的时候写了left = right = []，这样的话left和right指向同一个东西了，糖丸了。

python

n = int(input())
lst = list(map(int,input().split()))
ans = []
def back(s):
    root = s[0]
    left= []
    right = []
    for ch in s:
        if ch<root:
            left.append(ch)
        elif ch>root:
            right.append(ch)
    if left:
        back(left[:])
    if right:
        back(right[:])
    ans.append(root)
back(lst)
print(' '.join(map(str,ans)))

上面思路（回顾）

二叉搜索树的前序是 根左右，后序是 左右根。给出前序序列，要恢复出后序，可以按“当前子序列第一个是根，左子树是所有 < 根 的继续前序，右子树是所有 > 根 的继续前序”来分治。

你原来代码的两个问题：

写成 left = right = [] 会让 left 和 right 指向同一个列表（共享可变对象），导致数据混乱。
每次递归都在循环里构造新的 left/right 并切片 back(left[:]) 等，最坏情况（退化为链）会退化到 O(n^2) 时间并且频繁分配内存。

优化（O(n) 且只遍历一次）

用 前序 + 值上界 bound 的方法：维护一个全局指针 i 遍历前序数组。递归函数 dfs(bound) 的含义是：从当前位置 i开始，构造（并输出）所有值小于 bound 的节点的后序。步骤：

如果 i == n 或 pre[i] > bound：当前子树为空，返回。
取 root = pre[i]，i += 1。
先递归构造左子树：dfs(root)（左子树的节点必须 < root）
再递归构造右子树：dfs(bound)（右子树节点 < 原 bound 且 > root，因遍历顺序保证了它们会被正确处理）
最后把 root 输出到答案（后序顺序）。

这个方法只遍历 pre 一次，时间 O(n)，空间为递归栈深度（最坏 O(n)，平均 O(log n)）。

python

import sys
sys.setrecursionlimit(10000)

n = int(sys.stdin.readline().strip())
pre = list(map(int, sys.stdin.readline().split()))

ans = []
i = 0  # 全局索引

def dfs(bound):
    global i
    if i >= n or pre[i] > bound:
        return
    root = pre[i]
    i += 1
    # 左子树所有节点 < root
    dfs(root)
    # 右子树所有节点在 (root, bound)
    dfs(bound)
    ans.append(root)

# 初始 bound = +inf（这里用比可能值大的数）
dfs(10**9 + 7)
print(' '.join(map(str, ans)))

复杂度

时间：O(n)（每个元素只被读取一次并处理一次）
空间：O(n) 递归栈（最坏），额外输出数组 O(n)

【黄鹤鸣 2025fall-cs201 光华管理学院】思路：

前序的方式的访问顺序：从根节点到左子树再到右子树

中序的方式的访问顺序：从左子树到根节点再到右子树

后序的方式的访问顺序：从左子树到右子树再到根节点

二叉搜索树有大小的特点，通过以下while循环分左右子树

python

while i<len(pre) and pre[i]<root:
    i+=1

代码：

python

def build_postorder(pre):
    if not pre:
        return []

    root=pre[0]
    i=1
    while i<len(pre) and pre[i]<root:
        i+=1

    left=pre[1:i]
    right=pre[i:]
    return build_postorder(left)+build_postorder(right)+[root]
n=int(input())
pre=list(map(int,input().split()))
print(' '.join(map(str,build_postorder(pre))))

22275: 二叉搜索树的遍历 ​

22275: 二叉搜索树的遍历