type
status
password
date
slug
summary
category
URL
tags
icon
概述
树的问题最多的就是递归问题。树的问题基本就是树的遍历，创建，叶子节点，祖先节点，树的深度，树的路径几类问题。
- 叶子节点的判断：叶子节点的左右节点都为
None，所以我们可以通过node.left=None and node.right=None判断
- 最近公共祖先（最近公共父节点）：求p、q两个节点的公共父节点。分为3种情况，如下所示
- 树的路径：在递归函数中添加path参数，每一层遍历过程将该节点添加到路径中。如果是叶子节点，那么将该路径添加到外部变量ans中。
- 综合性：使用递归方法
树的遍历
- 深度遍历：例如，前中后序遍历。递归版和迭代版会访问三次节点，实质上前序遍历就是打印第1次访问节点；中序遍历，打印第2次；后序遍历，打印第3次。Morris遍历实质上会访问两次节点，前序遍历就是打印第1次访问节点；中序遍历，打印第2次；后序遍历，在第2次访问节点的时候，逆序遍历左子树的最右边界，最后逆序遍历整棵树的最右边界。
- 前序遍历：从树的根节点开始，先遍历左子树，然后遍历右子树。
- 中序遍历：先遍历左子树，然后访问根节点，然后遍历右子树。对于二叉搜索树，我们可以通过中序遍历得到一个递增的有序序列。
- 后序遍历：先遍历左子树，然后遍历右子树，最后访问树的根节点。
ㅤ | 递归版（最简单 注意空节点） | 迭代版(需要栈) | Morris |
前序遍历 | 打印Morris序的第一次 | ||
中序遍历 | 打印Morris序的第二次 | ||
后序遍历 | 到达Morris序的第二次时，逆序遍历当前结点左子树的最右边界 | ||
时间复杂度 | log(n) | log(n) | log(n) |
空间复杂度 | log(n) | log(n) | log(1) |
- 广度遍历：例如，层序遍历。从根节点出发，在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。
前中后遍历(递归版)
前序递归遍历
c++
python
c++
python
中序递归遍历
c++
python
c++
python
后序递归遍历
c++
python
c++
python
前中后遍历(迭代版)
在访问过左孩子之后，需要反过来访问其右孩子，所以，需要栈这种数据结构的支持。
后序遍历
对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为未访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都访问了三次，第1次是访问左节点的时候；第2次是访问完左节点，第1次出现在栈顶的时候；第3次是访问完右节点，第2次出现在栈顶的时候。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶，当第2次出现在栈顶的时候，就是后序遍历的顺序。
c++
python
Morris遍历
Morris遍历可以在线性时间内，只占用常数空间来实现二叉树的前中后遍历。Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。
Morris算法原理：记作当前节点为cur。
- 如果cur无左孩子，cur向右移动（cur=cur.right）
只访问一次
- 如果cur有左孩子，找到cur左子树上最右的节点，记为mostright
访问两次 - 如果mostright的right指针指向空，让其指向cur，cur向左移动（cur=cur.left）
第一次访问 - 如果mostright的right指针指向cur，让其指向空，cur向右移动（cur=cur.right）。此时左子树遍历完毕
第二次访问, 此刻左子树已经完成了访问
Morris算法本质：建立一种机制，对于没有左子树的节点只到达一次；对于有左子树的节点会到达两次，如果 mostright 指向null，则是第一次访问；如果 mostright 指向该节点自身，则是第二次访问。例如下面的二叉树，其Morris遍历顺序是1242513637
Morris序
前序遍历
Morris遍历加工成先序遍历的规则是：1. 如果一个节点只能被访问一次，被访问时打印。2.如果一个节点能被访问两次，在第一次被访问时打印。
中序遍历
Morris遍历加工成中序遍历的规则是：1. 如果一个节点只能被访问一次，被访问时打印。2.如果一个节点能被访问两次，在第二次被访问时打印。
后序遍历
后续遍历的基本思想是：逆序打印当前节点的左子树右边界。
Morris遍历加工成后序遍历的规则是
- 如果一个节点能被访问两次，在第二次被访问时逆序打印该节点左子树的右边界。
因为只有包含左子树的节点才能被访问两次
- 当所有节点遍历完后，单独逆序打印整棵树的右边界。
逆序打印左子树右边界
在代码实现之前，我们需要解决逆序打印的问题，并且将逆序打印的额外空间复杂度控制在O(1)。
解决方法：将右边界整体看成一个单向链表，将其中每个节点的right看成单项链表中节点的next并指向每个节点的父节点，没有父节点的指向null，每个节点的left指向保持不变，调整之后开始打印，打印结束后恢复right的原指向即可。
层序遍历
102. 二叉树的层序遍历 - 从上到下
- 首先根元素入队
- 当队列不为空的时候
- 求当前队列的长度
- 依次从队列中取 个元素进行拓展，然后进入下一次迭代
在上述过程中的第 次迭代就得到了二叉树的第 层的 个元素。
c++
python
107. 二叉树的层序遍历 II - 从下到上
与 从上到下的层序遍历 原理相同，区别是在添加到结果的时候，每次在第一个位置进行插入。
637. 二叉树的层平均值 - 力扣（LeetCode）
首先 从上到下的层序遍历 ，然后在计算每一层的平均值。
103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）
即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行
创建树
105. 从前序与中序遍历序列构造二叉树
前序遍历、中序遍历的基本性质如右图所示。只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，这样我们就得知了前序遍历中左子树与右子树的位置。
假设前序遍历中左子树序列的右边界是x
x - (preLeft+1) = (pIndex-1) - inLeft x = preLeft+pIndex - inLeft当我们知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。
解题思路
简化版本
106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）
我们可以发现后序遍历的数组最后一个元素代表的即为根节点。知道这个性质后，我们可以利用已知的根节点信息在中序遍历的数组中找到根节点所在的下标，然后根据其将中序遍历的数组分成左右两部分，左边部分即左子树，右边部分为右子树，针对每个部分可以用同样的方法继续递归下去构造。
x - postLeft = (pIndex-1) - inLeft x = postLeft+pIndex - 1 - inLeft注意这里有需要先创建右子树，再创建左子树的依赖关系。因为在后序遍历的数组中整个数组是先存储左子树的节点，再存储右子树的节点，最后存储根节点，如果按每次选择「后序遍历的最后一个节点」为根节点，则先被构造出来的应该为右子树。
与中序遍历、前序遍历对应的代码
叶子节点
输出二叉树中的叶子结点或统计二叉树中叶子结点的数目。可用三种遍历算法中的任何一种完成，在遍历过程中只需要测试每一个结点是否满足叶子结点的条件。下面以后序遍历为例，检测二叉树中的叶子节点。
判断叶子节点
根到叶子节点之和
给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123。
计算从根节点到叶节点生成的所有数字之和。
祖先节点
原理
我们递归遍历整棵二叉树，定义 表示 节点的子树中是否包含 节点或 节点，如果包含为 true，否则为 false。那么符合条件的最近公共祖先 一定满足如下条件：
其中 和 分别代表 节点的左孩子和右孩子。
- ：这个判断条件即是考虑了 恰好是 节点或 节点且它的左子树或右子树有一个包含了另一个节点的情况，因此如果满足这个判断条件亦可说明 就是我们要找的最近公共祖先。
- ：如果左子树包含的是 节点，那么右子树只能包含 节点，反之亦然。因为 节点和 节点都是不同且唯一的节点；那么，如果 节点在最近公共祖先的左子树， 节点就只能在最近公共祖先的右子树。因此只要判断左子树或者右子树是否包含 或者 节点，即可说明 就是我们要找的最近公共祖先。
236. 二叉树的最近公共祖先 - 力扣（LeetCode）
235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）
树的深度
最大深度
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
给定二叉树 [3,9,20,null,null,15,7]，最大深度为3
深度优先搜索
广度优先搜索：结合层序遍历进行计算
最小深度
给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
给定二叉树 [3,9,20,null,null,15,7]，最小深度为2
深度优先搜索
广度优先搜索：结合层序遍历进行计算
平衡树
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
树的路径
257. 二叉树的所有路径 - 力扣（LeetCode）
