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

2024-06-24 11:12

本文主要是介绍LeetCode 算法:二叉树的中序遍历 c++,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

题目

给定一个二叉树的根节点 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//     \//      4TreeNode* 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

这篇关于LeetCode 算法:二叉树的中序遍历 c++的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1089981

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象