我有必要跟你说一下perfect binary tree和full binary tree的区别,如果按照英文字面来理解的话,full binary tree翻译过来应该是满二叉树,其实不然,这样的字面翻译也是错误的,我们需要依据其具体的定义来理解,国外教材是这样定义full binary tree的:A full binary tree (sometimes referred to as a proper or plane binary tree) is a tree in which every node has either 0 or 2 children.从上述国外教材的原话中我们可以知道只要满足所有节点不是有0个就是有2个子节点的树就可以称为full binary tree,如下图:上面这个树在我们国内教材的定义上,不是满二叉树,但其确实对应了国外教材中所述的full binary tree的定义,你可以看到我在满二叉树的定义处指出国内教材中的满二叉树应对应国外教材中的perfect binary tree,来让我们看一下国外教材是怎么定义perfect binary tree的:A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level.下图即为一个满二叉树,即为perfect binary tree:此处我们要注意了如果一个二叉树是perfect binary tree那他一定是full binary tree,反之不成立。在部分国外教材中文译本上,perfect binary tree被翻译为完美二叉树,full binary被翻译为完满二叉树。下文中所有的满二叉树均指国内教材中有关满二叉树的定义,也就是perfect binary tree。
注:为向下取整符号,结果为不大于x的最大整数,例如为向上取整符号,结果为不小于x的最小整数,例如树中一个结点的子结点的个数称为结点的度(degree of node),度大于0的结点称为分支结点(branch node),度等于0的结点称为叶子结点(leaf node)或终端结点(terminal node)。树中结点最大的度数称为树的度。树的路径长度是从树的根节点到每一个结点的路径长度的总和。
if
块里面语句的顺序调换了一下而已。非递归后序遍历到某个结点时,栈中的序列即为从根节点到此结点的路径
vector<vector<int>>
,输入二叉树的每一层都要单独放在一个vector
里面,然后把所有层的vector
都打包在一个vector
里面返回,使用递归算法实现的代码如下:vector
里面,然后将其作为参数递归传下去,然后下一次递归的时候即遍历传入的当前一层的指针列表依次记录其中元素的值,然后插入结果集的vector
即可。12
,以及后序遍历序列为21
,我们可以看出如下两树均可满足相同的先序及后序遍历序列,所以其不能唯一地确定二叉树:12
和中序遍历序列21
,就能唯一地确定所要求得的二叉树为树1,因为树2的中序遍历序列为12
,就能把结点2牢牢地限制住其为1的左孩子。You may assume that duplicates do not exist in the tree.
说明树中没有重复元素了,所以我们可以直接在中序遍历的序列里查找根节点A所在的位置,依中序遍历规则可知,A前面的元素BD即为A作为根节点时的左孩子,A后面的元素GECHFI即为A作为根节点时的右孩子,然后再向下递归得到以结点B为根节点的子树,依次递归直至先序遍历序列完成一遍时算法结束。unordered_map
将其消除,用空间换时间,在递归之前,我们提前遍历中序遍历序列,将中序遍历的数值作为key和其在vector内的下标作为value,使用unordered_map
将其一一对应起来,这样我们可以直接使用二叉树遍历的数值(作为unordered_map
的key)来快速找到其在中序遍历序列中的下标(作为unordered_map
的value),从而省去了每一次进入使用for循环查找的过程,大大提升了算法的效率,代码如下:ltag
left
指针指向结点的左孩子left
指针指向结点的前驱rtag
right
指针指向结点的右孩子right
指针指向结点的后继这里的前驱和后继是相对于构建线索二叉树的遍历序列而言的。
看上图是要注意的一点就是:E和F,在变化之后,F由原来E的兄弟结点变为E的右孩子。
对于根节点来说,去除其右孩子的连线之后,左边的左子树部分就不动了,往下递归也是这个过程只操心右孩子,不再操心其左孩子
一定是按给定的从左到右的顺序连接
INT_MAX
的情况,所以我们在设定初始的min和max时要取LONG_MIN
和LONG_MAX
。注:AVL是最早实现的一种自平衡二叉搜索树,AVL的全称为Adelson-Velskii and Landis,这是以AVL树的三个创始人的名字首字母命名的,就像RSA算法一样。但有些国内的教材上会将平衡二叉树和AVL树放在一起谈,甚至说平衡二叉树就是AVL树,这样的说法是不严谨的,严格来说,AVL树是平衡二叉树的一种。