在二叉树题目选择什么遍历顺序是不少同学头疼的事情, 涉及到二叉树的构造,无论普通二叉树还是二叉搜索树一定前序,都是先构造中节点。 求普通二叉树的属性,一般是后序,一般要通过递归函数的返回值做计算。 求二叉搜索树的属性,一定是中序了,要不白瞎了有序性了。 注意在普通二叉树的属性中,我用的是一般为后序,例如单纯求深度就用前序, 二叉树:找所有路径也用了前序,这是为了方便让父节点指向子节点。 所以求普通二叉树的属性还是要具体问题具体分析
几乎刷完了力扣所有的树题,我发现了这些东西 |
---|
- 树的概述
- 1 树的存储结构
- 树的顺序存储
- 树的链表存储
- 树的基本操作
- 2 二叉树
- 2.1 二叉树的理论基础
- 2.2 二叉树类型
- 2.3 二叉树存储结构
- 2.4 二叉树的属性
- 二叉树:是否对称
- 递归方法:后序,比较的是根节点的左子树与右子树是不是相互翻转
- 迭代方法:使用队列/栈将两个节点顺序放入容器中进行比较
- 二叉树:求最大深度
- 递归方法:后序,求根节点最大高度就是最大深度,通过递归函数的返回值做计算树的高度
- 迭代方法:层序遍历
- 二叉树:求最小深度
- 递归方法:后序,求根节点最小高度就是最小深度,注意最小深度的定义
- 迭代方法:层序遍历
- 二叉树:求有多少个节点
- 递归方法:后序,通过递归函数的返回值计算节点数量
- 迭代方法:层序遍历
- 二叉树:是否平衡
- 递归方法:后序,注意后序求高度和前序求深度,递归过程判断高度差
- 迭代方法:效率很低,不推荐
- 二叉树:找所有路径
- 递归方法:前序,方便让父节点指向子节点,涉及回溯处理根节点到叶子的所有路径
- 迭代方法:一个栈模拟递归,一个栈来存放对应的遍历路径
- 二叉树:递归中如何隐藏着回溯
- 二叉树:求左叶子之和
- 递归方法:后序,必须三层约束条件,才能判断是否是左叶子。
- 迭代方法:直接模拟后序遍历
- 二叉树:求左下角的值
- 递归方法:顺序无所谓,优先左孩子搜索,同时找深度最大的叶子节点。
- 迭代方法:层序遍历找最后一行最左边
- 二叉树:求路径总和
- 递归方法:顺序无所谓,递归函数返回值为bool类型是为了搜索一条边,没有返回值是搜索整棵树。
- 迭代方法:栈里元素不仅要记录节点指针,还要记录从头结点到该节点的路径数值总和
- 二叉树:公共祖先问题
- 递归:后序,回溯,找到左子树出现目标值,右子树节点目标值的节点。
- 迭代:不适合模拟回溯
- 二叉树:是否对称
- 2.5 二叉树的基本操作
- 2.6 二叉搜索树的属性
- 二叉搜索树中的搜索
- 递归:二叉搜索树的递归是有方向的
- 迭代:因为有方向,所以迭代法很简单
- 是不是二叉搜索树
- 递归:中序,相当于变成了判断一个序列是不是递增的
- 迭代:模拟中序,逻辑相同
- 求二叉搜索树的最小绝对差
- 递归:中序,双指针操作
- 迭代:模拟中序,逻辑相同
- 求二叉搜索树的众数
- 递归:中序,清空结果集的技巧,遍历一遍便可求众数集合
- 迭代:模拟中序,逻辑相同
- 二叉搜索树转成累加树
- 递归:中序,双指针操作累加
- 迭代:模拟中序,逻辑相同
- 二叉搜索树的公共祖先问题
- 递归:顺序无所谓,如果节点的数值在目标区间就是最近公共祖先
- 迭代:按序遍历
- 二叉搜索树中的搜索
- 2.7 二叉搜索树的基本操作
- 构造二叉搜索树
- 递归:前序,数组中间节点分割
- 迭代:较复杂,通过三个队列来模拟
- 二叉搜索树中的插入操作
- 递归:顺序无所谓,通过递归函数返回值添加节点
- 迭代:按序遍历,需要记录插入父节点,这样才能做插入操作
- 二叉搜索树中的删除操作
- 递归:前序,想清楚删除非叶子节点的情况
- 迭代:有序遍历,较复杂
- 修剪二叉搜索树
- 递归:前序,数组中间节点分割
- 迭代:较复杂,通过三个队列来模拟
- 二叉搜索树的构建 基于数组的构建 插入构建
- 二叉搜索树的插入 插入到合适位置,插入后仍然是一颗二叉搜索树 递归算法
- 二叉搜索树的删除(分为删除节点为叶子节点、左子树为空、右子树为空、左右子树均不为空等四个方面,递归算法,删除后仍然是一颗二叉搜索树)
- 二叉搜索树的搜索 Olgn 递归算法](#二叉搜索树的搜索-Olgn-递归算法
- 二叉搜索树的遍历,特别是中序遍历 遍历结果为升序序列 递归算法
- 二叉搜索树的打印 树的前序遍历的应用 递归算法
- 以广义表形式的字符串构建二叉树
- 根据二叉树的前序 中序或中序 后序遍历结果构建二叉树
- 根据二叉树的根结点复制一颗二叉树
- 二叉树的结点总数
- 二叉树的根结点、孩子节点的获取
- 以广义表的形式打印二叉树
- 判断两颗二叉树是否相等
- n个结点构造多少种树
- 构造二叉搜索树
- 遍历二叉树
- 二叉树的遍历
- 普通二叉树的遍历---如果算法中多次涉及到对二叉树的遍历,普通的二叉树就需要使用栈结构做重复性的操作
- 深度优先遍历---先往深走,遇到叶子节点再往回走,这里的前中后序,其实指的就是中间节点的遍历顺序,中间节点的顺序就是所谓的遍历方式
- 广度优先遍历---一层一层的去遍历
- 线索二叉树的遍历---线索二叉树不需要使用栈结构,在遍历的同时,使用二叉树中空闲的内存空间记录某些结点的前趋和后继元素的位置(不是全部)
- 排序二叉树
- 二叉树:总结篇
- 3 平衡二叉树(AVL树)
- 4 B-Tree
- 5 红黑树
- 6 特殊树
- 6.1 区间树
- 6.2 前缀树---字典树
- 6.3 后缀平衡树
- 6.4 最小生成树
- 6.5 树状数组
- 8 回文树
- 9 哈夫曼树
- 10 并查集
- 11 森林---由 m(m >= 0)个互不相交的树组成的集合被称为森林
- 转换方法
- 森林 树和二叉树的转换
- 树转换为二叉树
- 二叉树转换树
- 森林转换为二叉树
- 二叉树转换森林
- 树和森林的遍历
- 转换方法
- 1 树的存储结构