企业官网建设流程全解析

大理石在哪些网站做宣传,注册网站云空间,直播app怎么开发,高端网站建设多少钱文章目录 94.二叉树的中序遍历(力扣题目) 题目描述 问题理解 题解 时间复杂度分析 图示解析 总结 94.二叉树的中序遍历(力扣题目) 题目描述 给定一个二叉树的根节点 root #xff0c;返回 它的 中序 遍历 。 示例 1#xff1a; 输入#xff1a;root [1,null,2,3]…文章目录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 { ListInteger result new ArrayList(); public ListInteger 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查找左节点不为空进入function32.进入节点3查找节点3的左节点找到左节点2进入左节点2。function3查找左节点不为空进入function23.进入节点2查找节点2的左节点左节点为空打印自身然后查找右节点右节点也为空返回上一级因为节点2已经打印完成所以是红色的状态。function2查找左节点为空打印自身查找右节点为空function2函数结束返回function3函数。因为function3是运行到一半进入function2函数所以调用function2函数结束之后回到function3。4.返回节点3遍历自身查找右节点找到右节点4进入右节点4。function3打印自身查找右节点不为空进入function45.进入节点4查找右节点为空打印自己查找右节点为空返回上一级节点3的左节点、自身、右节点已经完成返回根节点5打印自己然后查找右节点8进入又节点8。function4查找左节点为空打印自身查找右节点为空function4函数结束返回function3函数function3函数结束返回function5函数打印自身查找右节点不为空进入function86.进入节点8查找左节点不为空进入左节点7。function8查找左节点不为空进入function77.进入节点7查找左节点为空打印自身查找右节点为空返回父节点8。function8进入function7function7查找左节点为空打印自身function7查找右节点为空。function7函数结束返回function8函数。8.进入节点8打印自身查找左节点不为空进入节点9function7结束fuction8左节点查找操作完成打印自身查找function8的右节点不为空进入function99.进入节点9查找左节点为空打印自身查找右节点为空自此二叉树的中序遍历全部完成。fuction8查找右节点进入function9function9查找左节点为空打印自身function9查找右节点为空。function9函数结束返回function8函数function8函数查找右节点操作完成function8函数结束返回function5函数function5函数查找左节点操作完成function5函数结束自此程序运行完毕总结递归是“自身调用自身逐步拆解问题”本质是把复杂的大问题拆解为结构相同的小问题直到触达 “终止条件” 后回溯合并结果。递归非常适合二叉树的遍历已经完成了二叉树的中序遍历左根右可以试着自己完成二叉树的前序根左右和后序左右根遍历。如果你觉得这篇论文对你有帮助的话欢迎点赞、收藏并分享给身边在学算法的小伙伴