最近项目比较紧,忙了将近半个月,再加上现在看的书,比较难整理出技术文章。趁着过年,重新梳理一下2022年的规划,把节奏调整正常。但立的每周完成一道算法题的flag还是要实现的。
二叉树中序遍历,如果用递归来做的话,有水题的嫌疑。不过好久没做过二叉树的题目了,用来练练手也是可以的。
二叉树的中序遍历
给定一个二叉树的根节点 root ,返回它的 中序 遍历。
示例 1:
输入:root = [1,null,2,3]
输出:[1,3,2]
示例 2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
示例 4:
输入:root = [1,2]
输出:[2,1]
示例 5:
输入:root = [1,null,2]
输出:[1,2]
提示:
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
解题思路
解这道题的前提是知晓中序遍历是一种怎样的遍历模式。通过下图可以看出,中序遍历需要先遍历到最左侧节点,然后访问其父节点,然后访问该父节点的右子节点的最左侧节点,如此形成一个循环模式。
代码
按照该模式实现代码:
1 | var nodeValue []int |
本来以为这个代码手到擒来,没想到忘了判断root是否为nil,提交的时候出现panic错误。所以说,再简单的题目,也应该细心的应对。