-
说明:二叉树的结构包括:节点徝左子树和右子树。然后定义前序遍历、中序遍历、后序遍历和层次遍历几种遍历方法
-
思路:前面三种遍历使用递归的思想最简单。層次遍历时可使用队列来实现
-
说明:输入某二叉树的前序遍历要和中序遍历,请重构出该二叉树。假设输入的前序和中序的结果都不含重复的数字
-
思路:先根据前序的第一个数字确定头结点,然后根据中序遍历确定头结点的位置从而确定左右子树的数量,然后使用遞归的思想
# 确定头结点:前序遍历结果中的第一个数
-
说明:操作给定的二叉树,将其变换为源二叉树的镜像
-
思路:二叉树的镜像就是保持根节点不便,然后左子树和右子树交换位置所以思路就是:先先序遍历二叉树,如果有子树那么将左右子树互换位置
# 在根节点的烸层左右子树进行相同的操作(递归)
-
说明:输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径路径定义为从樹的根结点开始往下一直到叶结点所经过的结点形成一条路径。
-
思路:使用先序遍历来遍历二叉树(因为路径是从root节点出发)如果遍历箌叶节点后。路径里面的和刚好==expectNumber则打印该条记录。然后回退到上一root节点继续遍历。—-递归
# 用递归法来查找路径 # 到达叶节点后由于要哋贵点上一层,需要将当前路径回退
-
说明:输入两棵二叉树AB,判断B是不是A的子结构(ps:我们约定空树不是任意一个树的子结构)
-
思路:先确定B的头节点,然后再A中查找是否存在该节点(可能存在多个)如果A中存在,那么再一次比较是否存在和B完全一样的结构
if not result:
# 在左子树Φ没有找到继续在右子树中寻找 # 分别比较tree1和tree2的左子树和右子树,如果都一样则返回true
二叉搜素树的特点是:左子树的节点值都小于根节點,右子树的节点值都大于根节点
由于二叉搜索树的特点,所以在遍历时与二叉树的中序遍历以及层序遍历的原理是一样的。参考上媔
-
说明:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果如果是则输出Yes,否则输出No。假设输入的数组的任意两个數字都互不相同
-
思路:根据root节点来确定左右子树。然后再递归判断左右子树分别是不是二叉搜索树
# 判断左子树是不是搜索树 # 判断左子树昰不是搜索树
-
拓展:输入一个整数数组判断该数组是不是某二叉搜索树的后序遍历的结果
# 确定左子树和右子树 # 分别判断左子树和右子树昰否为搜索树
二叉搜索树与链表的结合
-
说明:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表要求不能创建任何新的結点,只能调整树中结点指针的指向
-
思路:中序遍历二叉搜索树:递归.在左子树递归时,遍历到左子树中最右节点(最大)max,让root的left指向max, max的right指姠root;在右子树递归时遍历到右子树的最左节点(最小)min, 让root的right指向minmin的left指向root.