105. 从前序与中序遍历序列构造二叉树

Posted on Edited on In Views: Word count in article: 684 Reading time ≈ 1 mins.

105. 从前序与中序遍历序列构造二叉树

题目链接：105. 从前序与中序遍历序列构造二叉树

题目描述

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

核心思考：分治法与递归构造

根据先序遍历和中序遍历的特性，我们可以利用分治（Divide and Conquer）的思想递归地构造二叉树：

  1. 确定根节点：先序遍历的第一个元素 preorder[0] 永远是当前子树的根节点。
  2. 划分左右子树：在中序遍历 inorder 中找到根节点的位置，记为索引 left_size。
    • inorder 中根节点左侧的所有元素构成了左子树的中序遍历。
    • inorder 中根节点右侧的所有元素构成了右子树的中序遍历。
  3. 确定子树范围：
    • 根据左子树的大小 left_size，我们可以从 preorder 中切分出左子树和右子树的先序遍历片段。
  4. 递归构造：分别对左、右子树调用构造函数，并将返回的子树根节点连接到当前根节点的 left 和 right 指针上。

通过这种方式，我们可以自顶向下地还原整棵二叉树的结构。

解题思路 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        # preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历
        if not preorder:
            return None
        
        # 1. 根节点即先序遍历的第一个元素
        root_val = preorder[0]
        
        # 2. 在中序遍历中定位根节点，划分左子树大小
        left_size = inorder.index(root_val)
        
        # 3. 递归构造左右子树
        # 左子树先序: preorder[1 : 1+left_size], 中序: inorder[0 : left_size]
        left_tree = self.buildTree(preorder[1:1+left_size], inorder[0:left_size])
        # 右子树先序: preorder[left_size+1 : ], 中序: inorder[left_size+1 : ]
        right_tree = self.buildTree(preorder[left_size+1:], inorder[left_size+1:])
        
        return TreeNode(root_val, left_tree, right_tree)

复杂度分析

  • 时间复杂度：$O(N^2)$。在当前 Python 实现中，由于 inorder.index() 的查表操作和列表切片（List Slicing）均为 $O(N)$，且递归调用了 $N$ 次。
  • 空间复杂度：$O(N)$。主要开销为递归调用的栈空间以及在每一次递归中创建的子数组切片。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

1
2
num1 num2 num3 ... numN
k

第一行输入数组，第二行输入整数 k。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import sys

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    # preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历
    if not preorder:
        return None

    # 1. 根节点即先序遍历的第一个元素
    root_val = preorder[0]

    # 2. 在中序遍历中定位根节点，划分左子树大小
    left_size = inorder.index(root_val)

    # 3. 递归构造左右子树
    # 左子树先序: preorder[1 : 1+left_size], 中序: inorder[0 : left_size]
    left_tree = self.buildTree(preorder[1:1+left_size], inorder[0:left_size])
    # 右子树先序: preorder[left_size+1 : ], 中序: inorder[left_size+1 : ]
    right_tree = self.buildTree(preorder[left_size+1:], inorder[left_size+1:])

    return TreeNode(root_val, left_tree, right_tree)

def main():
    data = sys.stdin.read().strip().split()
    k = int(data[-1])
    nums = list(map(int, data[:-1]))

    sol = Solution()
    result = sol.buildTree(nums, k)
    print(result)

if __name__ == "__main__":
    main()

运行示例：

1
echo -e "1 3 -1 -3 6 7\n3" | python solution.py