对于二叉排序树的ASL算法
二叉排序树的特点是左孩子小于根节点,右孩子大于根节点
之前寻找博客上计算ASL的算法时,看到用的是设置一个max值来判断是否换层,遍历二叉排序树,若是大于max则是属于同一层,赋值给max,直到找到小于max的节点就是下一层,但是对于如果一层中只有最后一个节点(即这一层最大的节点)有右孩子,max值就一直是增加的,则不会换层
解决方法
使用一个父节点数组和队列,有孩子节点则加入父节点队列,存储每一层的父节点数,一层结束后输出前面的父节点,只留下该层最后一父节点,则可以判断一层结束;
若节点队列为空且当前节点无孩子,则整个二叉排序树结束。