leetcode 94. Binary Tree Inorder Traversal 二叉树的中序遍历 (中等)
一、题目大意
给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。
示例 1:
输入:root = [1,null,2,3]
输出:[1,3,2]
示例 2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
提示:
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
来源:力扣(LeetCode)链接:https://leetcode.cn/problems/binary-tree-inorder-traversal著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二、解题思路
二叉树的中序遍历顺序为左 根 右,可以用递归和非递归来解。递归解法十分直接,对左了节点调用递归函数,根节点访问值,右子节点再调用递归函数。
非递归有两种方法,一种使用栈:从根节点开始,先将根节点压入栈,然后再将其所有左节点压入栈,然后取出栈顶节点,保存节点值,再将当前指针移到其右子节点上,若存在右子节点,则在下次循环时又可将其所有左子节点压入栈中,这样就保证了访问顺序为左 根 右。
三、解题方法
3.1 Java 实现 - 递归实现
复制代码
四、总结小记
2022/10/8 节后活有点多呀
版权声明: 本文为 InfoQ 作者【okokabcd】的原创文章。
原文链接:【http://xie.infoq.cn/article/95a9d3a5f3f52905415a0bb34】。文章转载请联系作者。
评论