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

本文涉及知识点　

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

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

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

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

1 Leetcode94 二叉树的中序遍历

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

示例1：

输入: [1,null,2,3]
   1
    \
     2
    /
   3输出: [1,3,2]

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

效果更好哈！

01 题目解析

• 思路

基本思路

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

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

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

02 动画演示

小蓝希望大家能够开开心心的学习，并能得到好的offer！也可以分享给身边朋友或者文末点个在看哟。

03 代码实现

1 c++版本

2 python版本

3 java版本