[leetcode二叉树系列]1 二叉树的中序遍历

[leetcode二叉树系列]1 二叉树的中序遍历

本文涉及知识点

二叉树的基本概念栈的运用

二叉树的基本概念和栈的相关概念前面已经介绍，忘记了的小伙伴复习后再看效果一定翻倍哟！

二叉树知识复习：[今天给二叉树加个BGM，二叉树唱歌了！]

栈知识复习：[leetcode栈队列]1 栈实现队列

1Leetcode94 二叉树的中序遍历

给定一个二叉树，返回它的中序 遍历。

示例1：

[1,null,2,3]    1     \      2     /    3 [1,3,2]

小蓝希望大家在此思考1分钟，

效果更好哈！

0

1

题目解析

思路

基本思路

对于一颗二叉树，我们能拿到根节点的root指针，首先访问的是根节点。但是我们需要按照左子树，根节点，右子树的顺序输出，那么什么数据结构有先出现后出来的特点，这就引入了栈。

从根节点访问，依次访问其左节点并入栈。

如果为NULL，弹出栈顶元素并将此元素的右节点放入栈中，重复此步骤。如上图D没有左右节点，此时弹出栈顶D，B，此时B存在右节点则入栈如下图。

02

代码实现

1c++版本

2python版本

3java版本

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。