一道算法题-二叉树的中序遍历

欢迎大家来到IT世界,在知识的湖畔探索吧!

最近项目比较紧，忙了将近半个月，再加上现在看的书，比较难整理出技术文章。趁着过年，重新梳理一下2022年的规划，把节奏调整正常。但立的每周完成一道算法题的flag还是要实现的。

二叉树中序遍历，如果用递归来做的话，有水题的嫌疑。不过好久没做过二叉树的题目了，用来练练手也是可以的。

二叉树的中序遍历

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

示例 1：

欢迎大家来到IT世界,在知识的湖畔探索吧!

输入：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

解题思路

代码位置：
https://github.com/shidawuhen/asap/blob/master/controller/algorithm/94-binary-tree-inorder-traversal.go

解这道题的前提是知晓中序遍历是一种怎样的遍历模式。通过下图可以看出，中序遍历需要先遍历到最左侧节点，然后访问其父节点，然后访问该父节点的右子节点的最左侧节点，如此形成一个循环模式。

代码

按照该模式实现代码：

var nodeValue []int func inorderTraversal(root *TreeNode) []int { nodeValue = make([]int, 0) if root == nil { return nodeValue } dsp(root) return nodeValue } func dsp(r *TreeNode) {  //访问到最左侧节点 if r.Left != nil { dsp(r.Left) }  //访问其父节点 nodeValue = append(nodeValue, r.Val)  //访问父节点的右子节点。右子节点开始dsp后，会找到该节点的最左侧节点，进入循环。 if r.Right != nil { dsp(r.Right) } } 

欢迎大家来到IT世界,在知识的湖畔探索吧!

本来以为这个代码手到擒来，没想到忘了判断root是否为nil，提交的时候出现panic错误。所以说，再简单的题目，也应该细心的应对。