【20230210】二叉树小结

二叉树的种类

二叉树的主要形式：满二叉树和完全二叉树。

满二叉树

深度为k，有2^k-1个节点的二叉树

完全二叉树

除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。

二叉搜索树

二叉搜索树是一个有序树

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

• 它的左、右子树也分别为二叉排序树

平衡二叉搜索树（AVL树）

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn，注意我这里没有说unordered_map、unordered_set，unordered_map、unordered_map底层实现是哈希表。

---

二叉树的存储方式

二叉树可以链式存储，也可以顺序存储。

链式存储方式就是用指针，顺序存储的方式就是用数组（了解）。

顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在各个地址的节点串联一起。

二叉树的遍历方式

1. 深度优先遍历：先往深处走，遇到叶子节点再往回走。

前、中、后序遍历

2. 广度优先遍历：一层一层的遍历。

层序遍历

二叉树的定义

链式存储的二叉树节点定义：

struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

---

二叉树的递归遍历

递归三要素：

1. 确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

2. 确定终止条件：写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

3. 确定单层逻辑：确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

---

二叉树的递归遍历

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。

迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了

---

例题：

1、从上到下打印二叉树、从上到下打印二叉树II、从上到下打印二叉树III（剑指1）

2、树的子结构、翻转二叉树、对称二叉树（剑指1）--树的子结构

---

关于二叉树的层序遍历：（广度优先算法）

用队列，用size记录每层的个数，每pop一个节点，判断其左右孩子是否为空，不为空就push进队列。

1.二叉树的层序遍历 、二叉树的层序遍历II、二叉树的右视图（判断当前层遍历的元素是否为最后一个元素，如果是的话就添加到数组里）

2.二叉树的层平均值（求均值的时候要做强制类型转换）

3.N叉树的层序遍历

注意N叉树节点的定义，节点的孩子是一个Node数组

class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};

关于二叉树的高度、深度等问题

• 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）

• 二叉树节点的高度：指从该节点到叶子节点的最长简单路径二叉树的最小深度边的条数后者节点数（取决于高度从0开始还是从1开始）

二叉树的最大深度、二叉树的最小深度

关于完全二叉树与平衡二叉树问题

完全二叉树的节点个数

后序遍历，在求完全二叉树的节点个数时，可以利用其性质，先一路向左，一路向右找最大深度，看看是否一致，相等的话，则这个节点往下为满二叉树，可以用公式2的n次方-1。

平衡二叉树

后序遍历，用返回-1的方式表达此时该节点已经不为平衡二叉树，注意这里获取高度时，如果为平衡二叉树，返回值为该节点目前的高度。与二叉树的最大深度这个题目搭配，可以很妙。

关于二叉树的路径问题

二叉树的所有路径

所有路径，肯定涉及回溯了，用中左右前序遍历。终止条件判断是否为叶子节点，中的处理要放在前面，在处理左右时要防止空指针异常。

注意这里的中处理时，将节点push进数组的操作要在终止条件之前做，因为最后一个节点也要放入数组中。