力扣-94.二叉树的中序遍历(Java递归)
文章目录
94.二叉树的中序遍历(力扣题目)
题目描述
问题理解
题解
时间复杂度分析
图示解析
总结
94.二叉树的中序遍历(力扣题目)
题目描述
给定一个二叉树的根节点root，返回它的中序遍历。
示例 1：
输入：root = [1,null,2,3]输出：[1,3,2]
示例 2：
输入：root = []输出：[]
示例 3：
输入：root = [1]输出：[1]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
问题理解
二叉树的中序遍历是先找当前节点是否有左节点，如果有就先找左节点，如果没有就遍历自己然后再找右节点，循环往复这个操作。这个文字问题我们能翻译成代码。
题解
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { List<Integer> result = new ArrayList<>(); public List<Integer> inorderTraversal(TreeNode root) { if(root != null) function(root); return result; } public void function(TreeNode node){ // 查找左节点操作 if(node.left != null) function(node.left); // 对自身进行操作,可以print自身，但是我们根据题目要求添加到一个列表中最后全部打印出来 result.add(node.val); // 查找右节点操作 if(node.right != null) function(node.right); } }时间复杂度分析
有多少个节点递归函数就要运行多少遍，所以时间复杂度为O(n)
图示解析
本图示解析为二叉树的中序递归遍历。本图示解析中绿色代表带输出节点，红色为已输出节点，白色为未查找节点，图示分析第二行文字描述为伪代码解析(functionx中x代表当前节点的值)。
1.以根节点5开始，查找节点的左子树，找到左节点3，进入左节点3。
function5查找左节点不为空进入function3
2.进入节点3，查找节点3的左节点，找到左节点2，进入左节点2。
function3查找左节点不为空，进入function2
3.进入节点2，查找节点2的左节点，左节点为空，打印自身，然后查找右节点，右节点也为空，返回上一级（因为节点2已经打印完成所以是红色的状态）。
function2查找左节点为空，打印自身，查找右节点为空，function2函数结束返回function3函数。因为function3是运行到一半进入function2函数，所以调用function2函数结束之后回到function3。
4.返回节点3，遍历自身，查找右节点，找到右节点4，进入右节点4。function3打印自身，查找右节点不为空，进入function4
5.进入节点4，查找右节点为空，打印自己，查找右节点为空返回上一级，节点3的左节点、自身、右节点已经完成，返回根节点5，打印自己然后查找右节点8，进入又节点8。
function4查找左节点为空，打印自身，查找右节点为空，function4函数结束返回function3函数，function3函数结束返回function5函数，打印自身，查找右节点不为空，进入function8
6.进入节点8，查找左节点不为空，进入左节点7。function8查找左节点不为空，进入function7
7.进入节点7，查找左节点为空，打印自身，查找右节点为空，返回父节点8。
function8进入function7，function7查找左节点为空，打印自身，function7查找右节点为空。function7函数结束返回function8函数。
8.进入节点8，打印自身，查找左节点不为空，进入节点9
function7结束，fuction8左节点查找操作完成，打印自身，查找function8的右节点不为空，进入function9
9.进入节点9，查找左节点为空，打印自身，查找右节点为空，自此二叉树的中序遍历全部完成。
fuction8查找右节点进入function9，function9查找左节点为空，打印自身，function9查找右节点为空。function9函数结束返回function8函数，function8函数查找右节点操作完成，function8函数结束返回function5函数，function5函数查找左节点操作完成，function5函数结束，自此程序运行完毕
总结
递归是“自身调用自身，逐步拆解问题”，本质是把复杂的大问题拆解为结构相同的小问题，直到触达 “终止条件” 后回溯合并结果。递归非常适合二叉树的遍历，已经完成了二叉树的中序遍历（左根右），可以试着自己完成二叉树的前序（根左右）和后序（左右根）遍历。
如果你觉得这篇论文对你有帮助的话，欢迎点赞、收藏并分享给身边在学算法的小伙伴