二叉树的中序遍历

题解思路

本题要求对二叉树进行中序遍历（Left-Root-Right）。输入数据采用层序存储方式

解题步骤

1. 构建二叉树：

   • 解析输入，将null转化为空节点。
   • 使用数组的索引方式构造二叉树。

2. 执行中序遍历：

   • 递归方法：先遍历左子树，再访问根节点，最后遍历右子树。
   • 使用深度优先搜索（DFS）实现。

3. 输出结果：

   • 采用空格分隔的方式输出遍历结果。

时间复杂度分析

• 构建二叉树：$O(n)$
• 中序遍历：$O(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 inorderTraversal(root):
    result = []
    stack = []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result

def build_tree(level_order):
    # 将层次遍历结果构建成二叉树
    if not level_order or level_order[0] == 'null':
        return None
    
    nodes = []
    index = 0
    root = TreeNode(int(level_order[index]))
    nodes.append(root)
    index += 1
    
    while index < len(level_order):
        node_val = level_order[index]
        if node_val != 'null':
            node = TreeNode(int(node_val))
            parent = nodes[(index - 1) // 2]
            if index % 2 == 1:
                parent.left = node
            else:
                parent.right = node
            nodes.append(node)
        index += 1
    
    return root

def main():
    import sys
    input_data = sys.stdin.read().strip()
    level_order = input_data.split()
    root = build_tree(level_order)
    result = inorderTraversal(root)
    print(" ".join(map(str, result)))

if __name__ == "__main__":
    main()

Java 代码

import java.util.*;

public class Main {
    // 定义二叉树节点类
    public static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int x) {
            val = x;
        }
    }
    
    // 中序遍历：非递归实现
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()){
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            result.add(current.val);
            current = current.right;
        }
        return result;
    }
    
    // 根据层次遍历结果构造二叉树
    public static TreeNode buildTree(String[] levelOrder) {
        if (levelOrder.length == 0 || levelOrder[0].equals("null"))
            return null;
        
        List<TreeNode> nodes = new ArrayList<>();
        int index = 0;
        TreeNode root = new TreeNode(Integer.parseInt(levelOrder[index]));
        nodes.add(root);
        index++;
        
        while (index < levelOrder.length) {
            String nodeVal = levelOrder[index];
            if (!nodeVal.equals("null")) {
                TreeNode node = new TreeNode(Integer.parseInt(nodeVal));
                TreeNode parent = nodes.get((index - 1) / 2);
                if (index % 2 == 1)
                    parent.left = node;
                else
                    parent.right = node;
                nodes.add(node);
            }
            index++;
        }
        return root;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<String> level_order = new ArrayList<>();
        while (scanner.hasNext()) {
            level_order.add(scanner.next());
        }
        scanner.close();
        String[] levelOrder = level_order.toArray(new String[0]);
        TreeNode root = buildTree(levelOrder);
        List<Integer> result = inorderTraversal(root);
        for (int i = 0; i < result.size(); i++) {
            System.out.print(result.get(i) + (i < result.size() - 1 ? " " : ""));
        }
    }
}

C++ 代码

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

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

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> s;
    TreeNode* current = root;
    while (current || !s.empty()) {
        while (current) {
            s.push(current);
            current = current->left;
        }
        current = s.top();
        s.pop();
        result.push_back(current->val);
        current = current->right;
    }
    return result;
}

// 根据层次遍历结果构造二叉树
TreeNode* buildTree(const vector<string>& level_order) {
    if (level_order.empty() || level_order[0] == "null")
        return nullptr;
    
    TreeNode* root = new TreeNode(stoi(level_order[0]));
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (i < level_order.size()) {
        TreeNode* current = q.front();
        q.pop();
        // 构造左子节点
        if (i < level_order.size() && level_order[i] != "null") {
            current->left = new TreeNode(stoi(level_order[i]));
            q.push(current->left);
        }
        i++;
        // 构造右子节点
        if (i < level_order.size() && level_order[i] != "null") {
            current->right = new TreeNode(stoi(level_order[i]));
            q.push(current->right);
        }
        i++;
    }
    return root;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string input;
    getline(cin, input);
    istringstream iss(input);
    vector<string> level_order;
    string token;
    while (iss >> token) {
        level_order.push_back(token);
    }
    
    TreeNode* root = buildTree(level_order);
    vector<int> result = inorderTraversal(root);
    for (int i = 0; i < (int)result.size(); i++) {
        cout << result[i] << (i < (int)result.size() - 1 ? " " : "\n");
    }
    return 0;
}

题目内容

给定一个二叉树的根节点$root$ ，输出它的中序遍历 。

输入描述

一行包含二叉树的序列化数组，节点值之间用空格隔开，空节点用null表示。

输出描述

输出一行，从$root_0$开始中序遍历，数字之间以空格分隔。

样例1

输入

1 null 2 3

输出

1 3 2

样例2

输入

1

输出

1

提示

• 树中节点数目在范围 $[0, 100]$内
• $-100 <= Node.val <= 100$