刷题笔记合集🔗

二叉树中序遍历

问题描述

小柯有一颗二叉树，她想通过中序遍历方式来遍历这棵树。中序遍历的顺序是：先访问左子树，再访问根节点，最后访问右子树。请您根据给定的二叉树结构描述字符串，输出该二叉树按照中序遍历结果字符串。

输入格式

输入为一个由大小写字母、左右大括号、逗号组成的字符串：字母代表一个节点值，左右括号内包含该节点的子节点。

左右子节点使用逗号分隔，逗号前为空则表示左子节点为空，没有逗号则表示右子节点为空。

二叉树节点数最大不超过 。

注：输入字符串格式是正确的，无需考虑格式错误的情况。

输出格式

输出一个字符串为二叉树中序遍历各节点值的拼接结果。

样例输入

a{b{d,e{g,h{,i}}},c{f}}

样例输出

dbgehiafc

数据范围

• 节点数
• 每个节点的值为单个字母（大小写均可）

题解

这道题目要求我们根据一个特殊格式的字符串来构建二叉树，然后返回中序遍历的结果。

首先来看看这个字符串格式：字母表示节点值，左右括号内表示子节点，逗号分隔左右子节点。比如 a{b,c} 表示根节点 a，左子节点是 b，右子节点是 c。

这道题的难点在于如何解析这个字符串并构建二叉树。我们可以利用栈结构来解决这个问题，思路如下：

1. 遍历输入字符串，使用一个栈保存字符。
2. 当遇到非 } 字符时，直接压入栈中。
3. 当遇到 { 字符时，记录它在栈中的索引位置。
4. 当遇到 } 字符时，我们就找到了一个完整的子树结构：
   • 根据之前记录的 { 的索引，我们能找到子树的根节点。
   • 根据 { 和 } 之间的内容，我们能分析出左右子节点。
   • 然后按照中序遍历规则（左-根-右）重组这个子树，替换掉栈中对应的部分。

通过这种方式，我们可以从内到外逐步解析整个二叉树结构，最终得到中序遍历的结果。

时间复杂度分析：我们只需要遍历输入字符串一次，对于每个字符的处理都是常数时间的操作，因此总体时间复杂度为 O(n)，其中 n 是输入字符串的长度。这对于题目给出的数据范围（节点数不超过100）是完全足够的。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 从输入读取字符串
s = input()

# 算法入口
def solve_tree(s):
    # 保存左括号索引的栈
    idx_stack = []
    # 保存字符的栈
    char_stack = []

    # 遍历输入字符串
    for c in s:
        # 遇到右括号时，处理一个完整子树
        if c == '}':
            # 弹出对应左括号的索引
            l_idx = idx_stack.pop()
            # 获取根节点值（左括号前一个字符）
            root = char_stack[l_idx - 1]
            
            # 提取括号内的子节点部分
            sub_tree = ''.join(char_stack[l_idx + 1:])
            # 分割左右子节点
            parts = sub_tree.split(',', 1)
            
            # 处理左子节点
            left = parts[0] if parts else ""
            # 处理右子节点
            right = parts[1] if len(parts) > 1 else ""
            
            # 删除已处理的子树部分
            char_stack = char_stack[:l_idx - 1]
            # 按中序遍历顺序（左-根-右）重建子树
            char_stack.append(left + root + right)
            continue
        
        # 遇到左括号，记录其索引
        if c == '{':
            idx_stack.append(len(char_stack))
        
        # 其他字符直接加入栈
        char_stack.append(c)
    
    # 最终栈中只剩下中序遍历结果
    return char_stack[0]

# 输出结果
print(solve_tree(s))

• Cpp

#include <bits/stdc++.h>
using namespace std;

// 解析二叉树并返回中序遍历结果
string inorder_traverse(const string& s) {
    // 保存左括号索引
    vector<int> br