求二叉树上结点的路径_剑指offer 二叉树

二叉树的镜像（简单）

操作给定的二叉树，将其变换为源二叉树的镜像。

思路：

1. 根节点左右节点调换位置
2. 递归
3. 注意判断空子树情况

二叉树的深度（简单）

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

思路：

1. 循环，类似广度优先
2. 每次循环时判断下一层是否有结点存在，存在则deep加一
3. 注意空树
4. 注意Proot（根节点）不能迭代，转换成list，即代码第12行a = [pRoot]

重建二叉树（中等）

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路：

1. 自己随便画个二叉树并写出前序中序遍历结果
2. 根据前序遍历找根节点，根据中序遍历找左右子树
3. 递归重复
4. 注意空子树情况

二叉搜索树与双向链表（中等）

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

注：二叉搜索树 --> 左子树 < 根节点 < 右子树

思路：

1. 针对左子树，将其构造成双向链表，并将其最右指针连接其父节点
2. 针对右子树，将其构成双向链表，并将其最左指针连接其父节点
3. 递归操作，返回值是树的最左节点
4. 注意树为空或只有根节点时返回自身

平衡二叉树（中等）

输入一棵二叉树，判断该二叉树是否是平衡二叉树。（不需要考虑其是不是排序二叉树）

平衡二叉树：一个二叉树 每个节点 的左右两个子树的高度差的绝对值不超过1。

思路：

1. 获取子树的高度（递归，每上升一层+1）
2. 判断左右子树高度差，相差超过1则返回False
3. 当且仅当左右子树均满足平衡时，整体树才平衡
4. 注意空树返回True

二叉树的下一个结点（中等）

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

思路：

1. 画出一个二叉树判断中序遍历规律4 、2 9、 2 -（1 3）9 -（7 10）、 7 - （6 8）、6 - （5 #） -- > 1 2 3 4 5 6 7 8 9 10
2. 规律：
   1. 找当前节点的右子树，有右子树，找到右子树的最左叶子结点 返回最左叶子结点
   2. 没有右子树，找其父节点，直到父节点的左节点为该节点 返回该节点
3. 注意空点为空

把二叉树打印成多行（中等）

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

思路：

1. 需要三个list，分别是最终结果、当前层树节点，当前层树节点的值
2. 最终结果中添加每层树节点的值[[],[],[]]
3. 每层数节点的值由当前层树节点list获得
4. 当前层树节点：
   1. 判断List长度，在长度范围内循环
   2. 每次弹出第一个节点，即为上一层父节点
   3. 判断该节点是否有左右子节点，有则添加
   4. 最终更新为当前层所有节点
5. 空树返回空

二叉搜索树的第k个结点（较难）

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

思路：

1. 二叉搜索树中序遍历结果就是从小到大的排序结点，将结果存到list中
2. 判断k的值是否满足（0，len(list)]，不满足返回None
3. 注意如果不是二叉搜索树考虑大小堆

树的子结构（较难）

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

思路：

1. 定义函数，判断tree2 和 tree1是否相等
   1. 允许tree2小于tree1
   2. 为了方便判断，使root1 = root2
   3. 递归
2. 递归判断在root1和root2不等时，root1的左右子树是否满足和tree2相等

注意15行，允许tree2先结束

序列化二叉树（较难）

请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，我们可以把一个只有根节点为1的二叉树序列化为"1,"，然后通过自己的函数来解析回这个二叉树

思路：

1. 序列化：
   1. 前序遍历，遇到没有子树（左或右）都用#表示出来
   2. 返回值是字符串形式
2. 反序列化：
   1. 将字符串变成列表
   2. 每次递归列表索引后移一位，判断当前值是否为#
   3. #退出当前次递归，否则递归得到左右子树

二叉搜索树的后序遍历结果（较难）

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

二叉搜索树：左子树<根<右子树

思路：

1. 根节点为数组的最后一个节点 root
2. 找到数组中第一个大于root的值，判断其之后是否有小于root的值，有返回False
3. 到此为止判断了根节点的左子树都小于root，右子树都大于root
4. 递归操作判断其左右子树是否符合3
5. 注意：
   1. 整体 空树返回False，只有根节点返回True
   2. 递归时空要返回True， 所以需要先赋值为True,并判断len>0才执行递归16-22

二叉树中和为某一值的路径（较难）

输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

输出结果：[ [],[],...,[] ]

思路：

1. 假设只有根节点，如果root的值等于给定值，返回 [ [root.val] ]
2. 左右子树递归，此时的给定值对应的参数应变成 给定值-root.val
3. 返回结果记得加上root路径
4. 注意空树返回[]

按之字形顺序打印二叉树（较难）

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推

思路：

1. 共需要4个数组，分别保存 当前层节点值、当前节点、下一层节点值、总结果
2. 初始当前层只有root
3. 对于当前层所有节点，保存到当前节点并将其左右子树分别存放到下一层节点中
4. 设置反序参数，如果为True则转置当前层节点数组
5. 将每一个当前层添加到总结果中
6. 将下一层赋值给当前层，改变反序参数

对称的二叉树（困难）

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

思路：

1. 定义一个递归函数判断给定的两个节点的子树是否对称
   1. 判断两节点p1, p2是否为空，空返回True
   2. 如果不为空并且 p1.val==p2.val，递归判断p1.left, p2.right 以及 p1.right, p2.left是否满足要求
   3. 过程中只要递归不到p1, p2均为空（不满足p1.val==p2.val），就说明有不等的，返回False
2. 确保pRoot的左右节点均存在或均不存在，调用1中递归函数

从上往下打印二叉树（困难）

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

思路：

1. support用于存放未添加左右节点的结点
2. 将support的第一个节点弹出并将其值存到result中
3. 判断第一个节点是否存在左右子树，存在则添加到support中
4. 重复上述操作直到support为空

最小K个数

输入整数数组

arr

，找出其中最小的

k

个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

思路：

1. 创建最大堆（数组表示）：
   1. 从子节点插入一个数
   2. 当前节点i的父节点索引：（i-1）// 2
   3. 如果当前节点值大于其父节点，交换位置
   4. 循环
2. 调整：
   1. 判断num和根节点的大小
   2. 当前节点i子节点索引：左：2*i + 1 右：2*i + 2
   3. 找到最大值索引
      1. 左右子节点中值最大的索引，如果num小于最大值，换位置
      2. 循环
3. 对于前K个值，创建最大堆
4. 对于剩下的值，调整最大堆