LeetCode94 二叉树的中序遍历

  • 作者:zyh
  • 分类:LeetCode
  • 发表日期:2020-07-10 14:29:44
  • 阅读(321)
  • 评论(0)

本题给定一棵二叉树,让用中序遍历的顺序,访问树的每一个节点,并把访问的节点按中序遍历的顺序存储到列表中。

其实这个示例,对于对二叉树中序遍历不熟悉的人不好看懂

 

先介绍一下二叉树的中序遍历

图上标红序号的顺序是最终每个节点在放到列表里的顺序,这里我借助栈来实现,根据栈的后进先出元则,以上图中的第二棵树为例,首先将根节点3压入栈,再将左子树5压入栈,再将2压入栈。此时2的左右子节点都为空,开始弹出,先弹出2,再弹出5。然后根据左中右原则,访问右节点,将6压入栈,因为6的左右节点也为空,所以将6弹出,然后在将3弹出。此时这棵二叉树的左半面的都已经遍历完毕。开始遍历右半面,只有一个4,将4压入栈然后在弹出,这棵二叉树的中序遍历就完毕了,列表存储的值的顺序应该是[2,5,6,3,4]。

下面来看代码:

LeetCode94 二叉树的中序遍历

 

提交评论

您尚未登录 :-( ,登录之后方可评论 登录 or 注册

评论列表

暂无评论