题目链接

树的不同形态

题目描述

给定一棵二叉树的层序遍历序列和中序遍历序列，求这棵二叉树的：

  1. 叶子节点（按照从左到右的顺序）。

  2. 先序遍历序列。

  3. 后序遍历序列。

解题思路

这个问题的核心是根据层序遍历和中序遍历序列来重建二叉树。一旦树被成功重建，获取叶子节点、先序遍历和后序遍历就都是常规的树遍历操作了。

重建二叉树的步骤：

  1. 确定根节点：

    在层序遍历序列中，第一个元素永远是整棵树（或当前子树）的根节点。

  2. 划分左右子树：

    找到这个根节点在中序遍历序列中的位置。中序遍历的特性是 [左子树的所有节点, 根节点, 右子树的所有节点]。因此，该位置左边的所有元素都属于根节点的左子树，右边的所有元素都属于根节点的右子树。

  3. 构建子树的遍历序列：

    • 我们已经根据中序遍历划分了左右子树的节点集合。

    • 现在，我们需要为左右子树分别找出它们自己的层序遍历序列。这可以通过遍历原始的层序遍历序列（跳过第一个根节点）来完成。对于序列中的每一个节点，我们检查它是否属于左子树的节点集合（可以预先将左子树的节点存入一个哈希表中以便快速查找）。如果是，就将其加入左子树的层序遍历序列；否则，加入右子树的层序遍历序列。

  4. 递归构建： 我们现在有了左子树的层序和中序序列，以及右子树的层序和中序序列。我们可以递归地调用相同的构建函数，来分别构建左子树和右子树，并将它们连接到根节点的 left 和 right 指针上。

递归终止条件：当中序遍历序列为空时，说明当前子树为空，返回 nullptr。

为了提高效率，我们可以预先将中序遍历序列的 (值 -> 索引) 关系存入一个哈希表（map），这样在第 2 步中就可以 时间找到根节点的位置。

重建后的操作：

  • 获取叶子节点：对重建后的树进行一次先序（或任何顺序）遍历。如果一个节点的左子节点和右子节点都为空，那么它就是叶子节点。

  • 先序遍历：执行标准的 根 -> 左 -> 右 遍历。

  • 后序遍历：执行标准的 左 -> 右 -> 根 遍历。

代码

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 存放三种遍历结果的辅助结构体
struct TraversalResults {
    vector<int> leaves;
    vector<int> preorder;
    vector<int> postorder;
};

// 递归构建二叉树
TreeNode* buildTree(const vector<int>& levelorder, const vector<int>& inorder) {
    if (levelorder.empty()) {
        return nullptr;
    }

    int rootVal = levelorder[0];
    TreeNode* root = new TreeNode(rootVal);

    auto it = find(inorder.begin(), inorder.end(), rootVal);
    int rootIndex = distance(inorder.begin(), it);

    vector<int> leftInorder(inorder.begin(), inorder.begin() + rootIndex);
    vector<int> rightInorder(inorder.begin() + rootIndex + 1, inorder.end());

    unordered_set<int> leftInorderSet(leftInorder.begin(), leftInorder.end());

    vector<int> leftLevelorder, rightLevelorder;
    for (size_t i = 1; i < levelorder.size(); ++i) {
        if (leftInorderSet.count(levelorder[i])) {
            leftLevelorder.push_back(levelorder[i]);
        } else {
            rightLevelorder.push_back(levelorder[i]);
        }
    }

    root->left = buildTree(leftLevelorder, leftInorder);
    root->right = buildTree(rightLevelorder, rightInorder);

    return root;
}

// 遍历并收集结果
void traverse(TreeNode* root, TraversalResults& results) {
    if (!root) {
        return;
    }

    // Preorder
    results.preorder.push_back(root->val);

    // Leaves
    if (!root->left && !root->right) {
        results.leaves.push_back(root->val);
    }

    traverse(root->left, results);
    traverse(root->right, results);

    // Postorder
    results.postorder.push_back(root->val);
}


void printVector(const vector<int>& vec) {
    for (size_t i = 0; i < vec.size(); ++i) {
        cout << vec[i] << (i == vec.size() - 1 ? "" : " ");
    }
    cout << endl;
}

vector<int> readVector(const string& line) {
    vector<int> vec;
    stringstream ss(line);
    int num;
    while (ss >> num) {
        vec.push_back(num);
    }
    return vec;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string level_line, in_line;
    getline(cin, level_line);
    getline(cin, in_line);

    vector<int> levelorder = readVector(level_line);
    vector<int> inorder = readVector(in_line);

    TreeNode* root = buildTree(levelorder, inorder);
    
    TraversalResults results;
    traverse(root, results);

    printVector(results.leaves);
    printVector(results.preorder);
    printVector(results.postorder);

    return 0;
}

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class TraversalResults {
    List<Integer> leaves = new ArrayList<>();
    List<Integer> preorder = new ArrayList<>();
    List<Integer> postorder = new ArrayList<>();
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String levelLine = sc.nextLine();
        String inLine = sc.nextLine();

        List<Integer> levelorder = parseLine(levelLine);
        List<Integer> inorder = parseLine(inLine);

        TreeNode root = buildTree(levelorder, inorder);
        
        TraversalResults results = new TraversalResults();
        traverse(root, results);

        printList(results.leaves);
        printList(results.preorder);
        printList(results.postorder);
    }

    private static List<Integer> parseLine(String line) {
        List<Integer> list = new ArrayList<>();
        if (line.isEmpty()) return list;
        String[] parts = line.split(" ");
        for (String part : parts) {
            list.add(Integer.parseInt(part));
        }
        return list;
    }

    private static void printList(List<Integer> list) {
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + (i == list.size() - 1 ? "" : " "));
        }
        System.out.println();
    }

    private static TreeNode buildTree(List<Integer> levelorder, List<Integer> inorder) {
        if (levelorder.isEmpty()) {
            return null;
        }

        int rootVal = levelorder.get(0);
        TreeNode root = new TreeNode(rootVal);

        int rootIndex = inorder.indexOf(rootVal);

        List<Integer> leftInorder = inorder.subList(0, rootIndex);
        List<Integer> rightInorder = inorder.subList(rootIndex + 1, inorder.size());

        Set<Integer> leftInorderSet = new HashSet<>(leftInorder);

        List<Integer> leftLevelorder = new ArrayList<>();
        List<Integer> rightLevelorder = new ArrayList<>();
        for (int i = 1; i < levelorder.size(); i++) {
            int val = levelorder.get(i);
            if (leftInorderSet.contains(val)) {
                leftLevelorder.add(val);
            } else {
                rightLevelorder.add(val);
            }
        }

        root.left = buildTree(leftLevelorder, leftInorder);
        root.right = buildTree(rightLevelorder, rightInorder);

        return root;
    }

    private static void traverse(TreeNode root, TraversalResults results) {
        if (root == null) {
            return;
        }

        // Preorder
        results.preorder.add(root.val);

        // Leaves
        if (root.left == null && root.right == null) {
            results.leaves.add(root.val);
        }

        traverse(root.left, results);
        traverse(root.right, results);

        // Postorder
        results.postorder.add(root.val);
    }
}

import sys
from collections import deque

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

def build_tree(levelorder, inorder):
    if not levelorder:
        return None
    
    root_val = levelorder[0]
    root = TreeNode(root_val)
    
    try:
        root_index = inorder.index(root_val)
    except ValueError:
        return None

    left_inorder = inorder[:root_index]
    right_inorder = inorder[root_index+1:]
    
    left_inorder_set = set(left_inorder)
    
    left_levelorder = []
    right_levelorder = []
    for val in levelorder[1:]:
        if val in left_inorder_set:
            left_levelorder.append(val)
        else:
            right_levelorder.append(val)
            
    root.left = build_tree(left_levelorder, left_inorder)
    root.right = build_tree(right_levelorder, right_inorder)
    
    return root

def get_traversals(root):
    leaves = []
    preorder = []
    postorder = []
    
    def traverse(node):
        if not node:
            return
        
        # Preorder
        preorder.append(node.val)
        
        # Leaves
        if not node.left and not node.right:
            leaves.append(node.val)
            
        traverse(node.left)
        traverse(node.right)
        
        # Postorder
        postorder.append(node.val)
        
    traverse(root)
    return leaves, preorder, postorder

def main():
    try:
        level_line = sys.stdin.readline().strip()
        in_line = sys.stdin.readline().strip()
        
        if not level_line or not in_line:
            return

        levelorder = list(map(int, level_line.split()))
        inorder = list(map(int, in_line.split()))
        
        root = build_tree(levelorder, inorder)
        
        leaves, preorder, postorder = get_traversals(root)
        
        print(" ".join(map(str, leaves)))
        print(" ".join(map(str, preorder)))
        print(" ".join(map(str, postorder)))

    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：二叉树、递归、分治

  • 时间复杂度：，其中 是二叉树的节点数。在 buildTree 函数的每一次递归调用中，我们都需要遍历层序序列来划分左右子树的层序序列，这个操作是 ，其中 是当前子树的节点数。对于一个不平衡的树（链状），递归深度为 ，总复杂度会达到 。对于平衡树，复杂度会好一些，约为 。重建树后，三次遍历的时间复杂度都是 。

  • 空间复杂度：。在最坏情况下（链状树），递归的每一层都需要创建新的 levelorder 和 inorder 列表/向量，总的空间消耗会达到 。同时，递归栈的深度也可能达到 。可以通过传递索引而非创建新数组来将空间复杂度优化到 。