ID: 2305

Difficulty: 5

题目内容

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

输入描述

输入的第一行包含两个整数 $n，m$ ，表示前序遍历数组 $preorder$ 和中序遍历数组 $inorder$ 的长度。
第二行包含 $n$ 个整数，表示前序遍历数组 $preorder$ 。
第三行包含 $m$ 个整数，表示中序遍历数组 $inorder$ 。

输出描述

输出一个数组，表示构造出的二叉树的层序遍历结果。末尾不保留多余null

样例1

输入

5 5
3 9 20 15 7
9 3 15 20 7

输出

3 9 20 null null 15 7

样例2

输入

1 1
-1
-1

输出

-1

提示

$1 <= preorder.length <= 3000$
$inorder.length == preorder.length$
$-3000 <= preorder[i], inorder[i] <= 3000$
$preorder$ 和 $inorder$ 均无重复元素
$inorder$ 均出现在 $preorder$
$preorder$ 保证为二叉树的前序遍历序列
$inorder$ 保证为二叉树的中序遍历序列

题解：从前序和中序遍历构造二叉树

解题思路

题目给定了二叉树的前序遍历和中序遍历序列，我们需要从这两种遍历序列中恢复出原始的二叉树结构，并最终返回该树的层序遍历结果。

首先，回顾二叉树的前序遍历和中序遍历的特点：

前序遍历：先访问根节点，再递归访问左子树，最后访问右子树。其顺序为：根 -> 左子树 -> 右子树。
中序遍历：递归访问左子树，再访问根节点，最后访问右子树。其顺序为：左子树 -> 根 -> 右子树。

通过这两个遍历序列，我们可以根据以下步骤恢复出二叉树：

步骤：

前序遍历的第一个元素一定是根节点。
根节点在中序遍历中分割了左右子树。根节点左边的元素为左子树，右边的元素为右子树。
在前序遍历中，根节点之后的元素分成左子树和右子树的元素，按照中序遍历中根节点的位置来划分。
递归构造左右子树。

递归构造树的步骤：

从前序遍历中取出第一个元素作为根节点。
在中序遍历中找到这个根节点的位置，将中序遍历分成左右子树。
在前序遍历中，依次处理属于左子树和右子树的元素，递归构造子树。

时间复杂度：

每次递归都要遍历一次中序数组来找到根节点的位置，因此时间复杂度是 O(n)。
对每个节点都进行一次递归，总的时间复杂度是 O(n)，其中 n 是节点数。

空间复杂度：

由于递归的深度是树的高度，最坏情况下空间复杂度为 O(n)。

Python 代码实现

# 二叉树的定义
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 构造二叉树的函数
def buildTree(preorder, inorder):
    # 辅助函数：根据前序遍历和中序遍历递归构造树
    def helper(preorder, inorder):
        if not preorder:
            return None
        root_val = preorder[0]
        root = TreeNode(root_val)
        root_index_inorder = inorder.index(root_val)
        
        # 左子树的中序遍历是中序遍历的根节点左边部分
        # 右子树的中序遍历是中序遍历的根节点右边部分
        root.left = helper(preorder[1: 1 + root_index_inorder], inorder[: root_index_inorder])
        root.right = helper(preorder[1 + root_index_inorder:], inorder[root_index_inorder + 1:])
        
        return root

    return helper(preorder, inorder)

# 层序遍历函数
def levelOrder(root):
    if not root:
        return []
    
    result = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append('null')
    
    # 去除末尾的多余 null
    while result and result[-1] == 'null':
        result.pop()
    
    return result

# 主函数，读取输入并执行
def main():
    # 读取输入
    n, m = map(int, input().split())
    preorder = list(map(int, input().split()))
    inorder = list(map(int, input().split()))
    
    # 构造二叉树
    root = buildTree(preorder, inorder)
    
    # 获取层序遍历结果
    result = levelOrder(root)
    
    # 输出结果
    print(" ".join(map(str, result)))

# 执行主函数
if __name__ == "__main__":
    main()

Java 代码实现

import java.util.*;

public class Main {
    // 二叉树节点定义
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) { this.val = val; }
    }

    // 构造二叉树的函数
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeHelper(preorder, inorder, 0, 0, inorder.length - 1);
    }

    // 递归辅助函数
    private static TreeNode buildTreeHelper(int[] preorder, int[] inorder, int preStart, int inStart, int inEnd) {
        if (preStart >= preorder.length || inStart > inEnd) return null;
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);

        // 查找根节点在中序遍历中的位置
        int rootIndexInInorder = inStart;
        while (inorder[rootIndexInInorder] != rootVal) {
            rootIndexInInorder++;
        }

        // 递归构造左右子树
        root.left = buildTreeHelper(preorder, inorder, preStart + 1, inStart, rootIndexInInorder - 1);
        root.right = buildTreeHelper(preorder, inorder, preStart + rootIndexInInorder - inStart + 1, rootIndexInInorder + 1, inEnd);

        return root;
    }

    // 层序遍历
    public static List<String> levelOrder(TreeNode root) {
        List<String> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                result.add(String.valueOf(node.val));
                queue.offer(node.left);
                queue.offer(node.right);
            } else {
                result.add("null");
            }
        }

        // 去除末尾的多余 null
        while (result.size() > 0 && result.get(result.size() - 1).equals("null")) {
            result.remove(result.size() - 1);
        }

        return result;
    }

    // 主函数
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] preorder = new int[n];
        int[] inorder = new int[m];

        for (int i = 0; i < n; i++) preorder[i] = sc.nextInt();
        for (int i = 0; i < m; i++) inorder[i] = sc.nextInt();

        // 构造树
        TreeNode root = buildTree(preorder, inorder);

        // 获取层序遍历结果
        List<String> result = levelOrder(root);

        // 输出结果
        System.out.println(String.join(" ", result));
    }
}

C++ 代码实现

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 二叉树节点定义
class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};

// 构造二叉树的函数
TreeNode* buildTreeHelper(vector<int>& preorder, vector<int>& inorder, int preStart, int inStart, int inEnd) {
    if (preStart >= preorder.size() || inStart > inEnd) return nullptr;
    int rootVal = preorder[preStart];
    TreeNode* root = new TreeNode(rootVal);

    // 查找根节点在中序遍历中的位置
    int rootIndexInInorder = inStart;
    while (inorder[rootIndexInInorder] != rootVal) {
        rootIndexInInorder++;
    }

    // 递归构造左右子树
    root->left = buildTreeHelper(preorder, inorder, preStart + 1, inStart, rootIndexInInorder - 1);
    root->right = buildTreeHelper(preorder, inorder, preStart + rootIndexInInorder - inStart + 1, rootIndexInInorder + 1, inEnd);

    return root;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    return buildTreeHelper(preorder, inorder, 0, 0, inorder.size() - 1);
}

// 层序遍历
vector<string> levelOrder(TreeNode* root) {
    vector<string> result;
    if (!root) return result;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        if (node != nullptr) {
            result.push_back(to_string(node->val));
            q.push(node->left);
            q.push(node->right);
        } else {
            result.push_back("null");
        }
    }

    // 去除末尾的多余 null
    while (result.size() > 0 && result[result.size() - 1] == "null") {
        result.pop_back();
    }

    return result;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> preorder(n), inorder(m);

    for (int i = 0; i < n; i++) cin >> preorder[i];
    for (int i = 0; i < m; i++) cin >> inorder[i];

    // 构造树
    TreeNode* root = buildTree(preorder, inorder);

    // 获取层序遍历结果
    vector<string> result = levelOrder(root);

    // 输出结果
    for (int i = 0; i < result.size(); i++) {
        if (i != 0) cout << " ";
        cout << result[i];
    }
    cout << endl;

    return 0;
}

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

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

题目内容

输入描述

输出描述

样例1

样例2

提示

题解：从前序和中序遍历构造二叉树

解题思路

步骤：

递归构造树的步骤：

时间复杂度：

空间复杂度：

Python 代码实现

Java 代码实现

C++ 代码实现

Status

Development

Support

#P4064. 从前序与中序遍历序列构造二叉树 ⬅ 上一题 ➡ 下一题

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

题目内容

输入描述

输出描述

样例1

样例2

提示

题解：从前序和中序遍历构造二叉树

解题思路

步骤：

递归构造树的步骤：

时间复杂度：

空间复杂度：

Python 代码实现

Java 代码实现

C++ 代码实现

Status

Development

Support

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