【华为机试】2023年真题B卷（python）-二叉树中序遍历

一、题目

题目描述：

根据给定的二叉树结构描述字符串，输出该二叉树按照中序遍历结果字符串。中序遍历顺序为：左子树，根结点，右子树。

二、输入输出

输入描述：
由大小写字母、左右大括号、逗号组成的字符串:字母代表一个节点值，左右括号内包含该节点的子节点。
左右子节点使用逗号分隔，逗号前为空则表示左子节点为空，没有逗号则表示右子节点为空。
二叉树节点数最大不超过100。
注:输入字符串格式是正确的，无需考虑格式错误的情况。
输出描述：
输出一个字符串为二叉树中序遍历各节点值的拼接结果。

三、示例

示例 1???
输入输出示例仅供调试，后台判题数据一般不包含示例
输入:
a{b{d,e{g,h{,I}}},c{f}}
输出:
dbgehIafc

四、要求

时间限制：C/C++ 1秒，其他语言 2秒
空间限制：C/C++262144K，其他语言524288K

五、解题思路

1. 创建一个空栈?stack?和一个空列表?positions，用于记录左括号的位置。
2. 遍历输入字符串?input_str?中的每个字符：
   • 如果当前字符是左括号?{，将当前栈的长度加入?positions?列表，并将当前字符入栈。
   • 如果当前字符是右括号?}，取出?positions?列表中最后一个位置的元素作为根节点，将根节点、左子树和右子树拼接成一个新的字符串，并将新字符串入栈。
   • 如果当前字符不是括号，则将当前字符入栈。
3. 输出栈中唯一的元素，即为中序遍历结果。

六、参考代码?

# -*- coding: utf-8 -*-
'''
@File    :   2023-B-二叉树中序遍历.py
@Time    :   2023/12/17 13:13:56
@Author  :   mgc 
@Version :   1.0
@Desc    :   None
'''

def inorder_traversal(input_str):
    stack = []  # 栈，用于构建二叉树
    positions = []  # 记录左括号的位置

    i = 0
    while i < len(input_str):
        if input_str[i] == '{':
            positions.append(len(stack))
            stack.append(input_str[i])
        elif input_str[i] == '}':
            root = stack[positions[-1] - 1]
            left = ""
            right = ""
            new_str = ""
            for ele in stack[(positions[-1] + 1):]:
                new_str += ele
            new_list = new_str.split(",")
            if len(new_list) == 1:
                left = new_list[0]
            else:
                left = new_list[0]
                right = new_list[1]

            stack = stack[:positions[-1] - 1]
            stack.append(left + root + right)
            positions.pop()
        else:
            stack.append(input_str[i])
        i += 1

    return stack[0]

input_str = input()
result = inorder_traversal(input_str)
print(result)