前言:
由于二叉树这一章的题型比较多,涉及到的递归程序也较多,所以单开一个随笔来记录这个学习过程,希望对读者有帮助。
理论知识基础
在二叉树的选择题中,常常会涉及到对于最多或最少结点、最大或最小高度、求叶子结点个数这几类经典的问题。
上机题
1.二叉树的建立和遍历
- 这题考察输入每个结点和其左右子树,然后前序遍历。
- 这题考察给你所有叶子结点,让你建立一颗满二叉树。
- 建立二叉树遍历求深度
- 通过中序和后序构建树,然后再层序输出
- 找最大深度,以及最小且最长的路径
- 通过后序遍历序列 建立层次遍历序列
2.前序、中序、后序遍历的转换
给出了中序以后,给定前序或后序都可以确定唯一的一棵树。
不给出中序则无法确定。
P1827 [USACO3.4] 美国血统 American Heritage
- 这题给出前序和中序求后序
- 这题给出中序和后序求前序