数据结构和算法基础篇二叉树的中序遍历

上一篇文章中,我们介绍了栈来实现二叉树的前序遍历。这一篇文章,我们还使用栈来实现二叉树的中序遍历。

所谓二叉树的中序遍历,就是先访问左子树,然后访问根节点,然后右子树。然后左子树的访问还是满足这个顺序。不熟悉遍历过程的朋友可以百度谷歌搜一下遍历的示例。

下面我们来看Leetcode上面的一道题目,怎么实现中序遍历。

94. Binary Tree Inorder Traversal

Given a binary tree, return theinordertraversal of its nodes' values.

Example:

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

Output:[1,3,2]

题目的要求给定了一个二叉树的根节点,然后要求输出中序遍历的结果。

二叉树的遍历采用递归版本的思路很简单,就是先递归左子树,然后根节点,最后右子树。参考代码如下:

递归遍历的核心代码其实就是三行:递归调用左子树,处理当前节点,递归右子树。递归的出口就是节点为空。

下面我们来看看非递归版本的思路。

非递归版本的思路就是,从根节点开始,一直找到最左边的节点。因为这个节点才是第一个节点。那么我们可以从根节点开始压入栈,如果当前节点存在左子树就继续压栈直到叶子节点。

当压入到了叶子节点了,就开始从栈中取一个节点。然后输出这个节点数据,接着处理这个节点的节点。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180726G11GL400?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动