LeetCode 算法:二叉树的中序遍历 c++

news/2024/7/17 7:38:48

原题链接🔗:二叉树的中序遍历
难度:简单⭐️

题目

给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。

示例 1
在这里插入图片描述

输入:root = [1,null,2,3]
输出:[1,3,2]

示例 2

输入:root = []
输出:[]

示例 3

输入:root = [1]
输出:[1]

提示

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

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

二叉树遍历

二叉树遍历是数据结构中的一个重要概念,它涉及到按照特定的顺序访问二叉树中的所有节点。二叉树的遍历主要有以下几种方式:

  1. 前序遍历(Pre-order Traversal)

    • 访问根节点。
    • 遍历左子树(前序)。
    • 遍历右子树(前序)。
  2. 中序遍历(In-order Traversal)

    • 遍历左子树(中序)。
    • 访问根节点。
    • 遍历右子树(中序)。
  3. 后序遍历(Post-order Traversal)

    • 遍历左子树(后序)。
    • 遍历右子树(后序)。
    • 访问根节点。
  4. 层序遍历(Level-order Traversal)

    • 使用队列实现,按照从上到下,从左到右的顺序访问每个节点。

每种遍历方式都有其特点和应用场景。下面是每种遍历方式的C++实现示例:

前序遍历

void preOrder(TreeNode* node) {
    if (node == nullptr) return;
    std::cout << node->val << " ";  // 访问根节点
    preOrder(node->left);            // 遍历左子树
    preOrder(node->right);           // 遍历右子树
}

中序遍历

void inOrder(TreeNode* node) {
    if (node == nullptr) return;
    inOrder(node->left);             // 遍历左子树
    std::cout << node->val << " ";  // 访问根节点
    inOrder(node->right);            // 遍历右子树
}

后序遍历

void postOrder(TreeNode* node) {
    if (node == nullptr) return;
    postOrder(node->left);           // 遍历左子树
    postOrder(node->right);          // 遍历右子树
    std::cout << node->val << " ";  // 访问根节点
}

层序遍历

void levelOrder(TreeNode* root) {
    if (root == nullptr) return;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        std::cout << node->val << " ";
        if (node->left != nullptr) q.push(node->left);
        if (node->right != nullptr) q.push(node->right);
    }
}

在实际应用中,选择哪种遍历方式取决于你需要解决的问题。例如,如果你需要先访问根节点以决定后续操作,可能会选择前序遍历;如果你需要先访问所有子节点再访问根节点,可能会选择后序遍历;如果你需要按照树的层次顺序访问节点,可能会选择层序遍历。中序遍历通常用于二叉搜索树,因为它可以按照升序访问所有节点。

题解

递归法

  1. 解题思路

二叉树的中序遍历解题思路主要基于深度优先搜索(DFS)策略。以下是中序遍历的一般步骤和思路:

  1. 理解中序遍历的顺序:中序遍历的特点是先访问左子树,然后是根节点,最后是右子树。

  2. 递归方法

    • 从根节点开始,递归地执行中序遍历。
    • 对于每个节点,首先递归地遍历其左子节点。
    • 访问当前节点(根节点)。
    • 然后递归地遍历其右子节点。
  3. 使用栈实现非递归遍历

    • 使用一个栈来辅助实现非递归的中序遍历。
    • 从根节点开始,将其压入栈中。
    • 弹出栈顶元素,访问它的值,然后将其右子节点压入栈中。
    • 如果弹出的节点有左子节点,将其左子节点压入栈中,重复上述步骤。
    • 当栈为空时,遍历结束。
  4. 处理边界条件:确保在递归或非递归方法中处理空节点的情况。

  5. 代码实现

    • 定义一个二叉树节点结构,通常包含节点的值和指向左右子节点的指针。
    • 实现中序遍历函数,可以是递归形式或使用栈的非递归形式。
  6. 测试:使用不同的二叉树结构来测试你的中序遍历算法,确保它可以正确地按照中序遍历的顺序访问所有节点。

  7. 优化:考虑算法的时间复杂度和空间复杂度。对于递归方法,注意递归深度可能影响性能;对于非递归方法,注意栈的使用可能会增加空间开销。

  8. 考虑特殊情况:例如,二叉树只有一个节点或没有节点,或者二叉树是一条链(所有节点只有左或只有右子节点)。

  9. 使用辅助数据结构:如果需要存储遍历结果,可以使用数组、列表或其他数据结构来收集遍历过程中访问的节点值。

  1. 复杂度:空间复杂度O(n),时间复杂度O(n)。
  2. c++ demo
#include <iostream>
#include <vector>

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

void inorderTraversal(TreeNode* node) {
    if (node == nullptr) {
        return;
    }
    // 访问左子树
    inorderTraversal(node->left);
    // 访问根节点
    std::cout << node->val << " ";
    // 访问右子树
    inorderTraversal(node->right);
}

int main() {
    // 构建一个示例二叉树
    //       1
    //      / \
    //     2   3
    //     \
    //      4
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->right = new TreeNode(4);

    // 执行中序遍历
    std::cout << "Inorder traversal of the binary tree is: ";
    inorderTraversal(root);

    // 清理内存
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}
  • 输出结果:

Inorder traversal of the binary tree is: 2 4 1 3


http://lihuaxi.xjx100.cn/news/2233105.html

相关文章

【JS逆向百例】某点数据逆向分析,多方法详解

前言 最近收到粉丝的私信&#xff0c;其在逆向某个站点时遇到了些问题&#xff0c;在查阅资料未果后&#xff0c;来询问K哥&#xff0c;K哥一向会尽力满足粉丝的需求。网上大多数分析该站点的教程已经不再适用&#xff0c;本文K哥将提供 3 种解决方案&#xff0c;对于 webpack…

适合学习通考试的搜题软件?四个公众号和软件推荐清单! #微信#微信#其他

积极参加社团活动和实践项目&#xff0c;可以帮助大学生拓宽人脉圈和锻炼实际操作能力。 1.酷学习 酷学习网站全内容全覆盖&#xff0c;其涵盖面包括了从小学到大学庞大的知识群 内容主要包括数学、物理、化学、英语、生物、语文、历史、地理的教学视频&#xff0c;包括小升…

如何高效配置与使用Pip换源

目录 1. Pip源的基本概念 1.1 常见的国内镜像源 2. 临时换源 2.1 使用命令行参数指定镜像源 2.2 安装多个包时指定镜像源 3. 永久换源 3.1 修改用户级配置文件 3.1.1 创建和编辑配置文件 3.2 修改全局配置文件 3.2.1 创建和编辑全局配置文件 4. 验证换源配置 5. 切…

【组件缓存相关生命周期函数】

在Vue开发中&#xff0c;有时需要在组件被激活或者被缓存时执行某些操作。为此&#xff0c;Vue 提供了组件缓存相关的生命周期函数&#xff0c;可以监听组件被激活和组件被缓存的事件。当组件被激活时&#xff0c;会触发组件的onActivated( )生命周期函数;当组件被缓存时&#…

农业四情监测设备——提高农业生产的效率和质量

TH-Q1农业四情监测设备是用于实时监测农业领域的四大关键监测内容的设备&#xff0c;这些内容包括土壤墒情、苗情、病虫情和灾情。以下是关于农业四情监测设备的详细介绍&#xff1a; 主要用于实时测量农田土壤的水分状况。包含土壤湿度传感器、土壤温度传感器等&#xff0c;安…

板凳-------第58章SOCKET:TCP/IP网络基础

58.1 互联网 互联网会将不同的计算机网络连接起来并允许位于网络中的主机相互之间进行通信。互联网的目标是隐藏不同物理网络的细节以便向互联网中的所有主机呈现一个统一的网络架构&#xff0c;TCP/IP已经成了使用最为广泛的协议套件了&#xff0c; 术语Internet被用来指将全球…

在超线程CPU上切换到另一个线程

在超线程CPU上切换到另一个线程&#xff0c;主要涉及到的是上下文切换的过程。超线程技术允许单个CPU核心同时执行多个线程&#xff0c;提高了CPU的并行计算效率。当需要从一个线程切换到另一个线程时&#xff0c;CPU会进行一系列的操作来确保线程之间的顺利切换。 首先&#…

谷歌浏览器截图

一 右击&#xff0c;然后点击检查&#xff1b; 二 然后ctrlshiftp,运行命令&#xff1b; 三 3.1搜索截图&#xff1a; 如果你设置为中文&#xff0c;搜索截图&#xff0c;选择你想要的截图类型&#xff1b; 如果你是在英文情况下&#xff1a; 输入capture full size 来过滤…