学网站开发的培训学校,网站怎么建设,开发一个手游游戏要多少钱,最专业的网站开发公司哪家最专业各个部分题目的代码题解都在我往日的二叉树的博客中。 (day14到day22) 目录 二叉树理论基础二叉树的遍历方式深度优先遍历广度优先遍历 求二叉树的属性二叉树的修改与制造求二叉搜索树的属性二叉树公共最先问题二叉搜索树的修改与构造总结 二叉树理论基础
二叉树的理论基础参…各个部分题目的代码题解都在我往日的二叉树的博客中。 (day14到day22) 目录 二叉树理论基础二叉树的遍历方式深度优先遍历广度优先遍历 求二叉树的属性二叉树的修改与制造求二叉搜索树的属性二叉树公共最先问题二叉搜索树的修改与构造总结 二叉树理论基础
二叉树的理论基础参考我的朱提第一篇二叉树的文章 链接: day14 得注意各种二叉树的种类、存储方式、遍历方式、定义方式。
二叉树的遍历方式
深度优先遍历
链接: day14 二叉树前中后序的递归三部曲 二叉树前中后序的迭代法 二叉树前中后序的迭代法的统一形式
广度优先遍历
链接: day15 二叉树的层序遍历
求二叉树的属性
二叉树是否对称 递归后序比较的是根节点的左子树与右子树是不是相互翻转 迭代使用队列/栈将两个节点顺序放入容器中进行比较二叉树求最大深度 递归后序求根节点最大高度就是最大深度通过递归函数的返回值做计算树的高度 迭代层序遍历二叉树求最小深度 递归后序求根节点最小高度就是最小深度注意最小深度的定义 迭代层序遍历二叉树求有多少个节点 递归后序通过递归函数的返回值计算节点数量 迭代层序遍历二叉树是否平衡 递归后序注意后序求高度和前序求深度递归过程判断高度差 迭代效率很低不推荐二叉树找所有路径 递归前序方便让父节点指向子节点涉及回溯处理根节点到叶子的所有路径 迭代一个栈模拟递归一个栈来存放对应的遍历路径二叉树递归中如何隐藏着回溯 详解二叉树找所有路径 中递归如何隐藏着回溯二叉树求左叶子之和 递归后序必须三层约束条件才能判断是否是左叶子。 迭代直接模拟后序遍历二叉树求左下角的值 递归顺序无所谓优先左孩子搜索同时找深度最大的叶子节点。 迭代层序遍历找最后一行最左边二叉树求路径总和 递归顺序无所谓递归函数返回值为bool类型是为了搜索一条边没有返回值是搜索整棵树。 迭代栈里元素不仅要记录节点指针还要记录从头结点到该节点的路径数值总和
二叉树的修改与制造
翻转二叉树 递归前序交换左右孩子 迭代直接模拟前序遍历构造二叉树 递归前序重点在于找分割点分左右区间构造 迭代比较复杂意义不大构造最大的二叉树 递归前序分割点为数组最大值分左右区间构造 迭代比较复杂意义不大合并两个二叉树 递归前序同时操作两个树的节点注意合并的规则 迭代使用队列类似层序遍历
求二叉搜索树的属性
二叉搜索树中的搜索 递归二叉搜索树的递归是有方向的 迭代因为有方向所以迭代法很简单是不是二叉搜索树 递归中序相当于变成了判断一个序列是不是递增的 迭代模拟中序逻辑相同求二叉搜索树的最小绝对差 递归中序双指针操作 迭代模拟中序逻辑相同求二叉搜索树的众数 递归中序清空结果集的技巧遍历一遍便可求众数集合二叉搜索树转成累加树 递归中序双指针操作累加 迭代模拟中序逻辑相同
二叉树公共最先问题
二叉树的公共祖先问题 递归后序回溯找到左子树出现目标值右子树节点目标值的节点。 迭代不适合模拟回溯二叉搜索树的公共祖先问题 递归顺序无所谓如果节点的数值在目标区间就是最近公共祖先 迭代按序遍历
二叉搜索树的修改与构造
二叉搜索树中的插入操作 递归顺序无所谓通过递归函数返回值添加节点 迭代按序遍历需要记录插入父节点这样才能做插入操作二叉搜索树中的删除操作 递归前序想清楚删除非叶子节点的情况 迭代有序遍历较复杂 修剪二叉搜索树 递归前序通过递归函数返回值删除节点 迭代有序遍历较复杂构造二叉搜索树 递归前序数组中间节点分割 迭代较复杂通过三个队列来模拟
总结
涉及到二叉树的构造无论普通二叉树还是二叉搜索树一定前序都是先构造中节点。
求普通二叉树的属性一般是后序一般要通过递归函数的返回值做计算。
求二叉搜索树的属性一定是中序。
注意在普通二叉树的属性中我用的是一般为后序例如单纯求深度就用前序【二叉树找所有路径】也用了前序这是为了方便让父节点指向子节点。
所以求普通二叉树的属性还是要具体问题具体分析。
参考文档
链接: 二叉树总结
