二叉排序树的按层遍历

　　二叉排序树的按层遍历与广度优先遍历一样，不过是把遍历输出按层展示。第三层如下图所示。

　　思路分析：采用两个列表，列表1装上一层的节点引用，列表2装下一层的节点引用。如果需要循环向下，则把上一层列表全清空，然后把下一层中的节点全部放进上一层节点中。遍历上一层节点的左右指针，就可以获得下一层的全部节点。二叉排序树按层遍历的算法图解如下图所示。

　　以此类推获得下一层的全部节点。

　　程序代码：

　　运行结果：

　　练习１：把上例的levelTraverse(self)改为levelTraverse(self,　k)，k是指定层数（1≤k≤5），即只是打出k层，其它层不输出。

　　求二叉树的最大深度、最小深度

　　求二叉树的最大深度（高度）和最小深度。本来是两道题，这里把两道题合成一道。最大深度是从根节点到最远的叶子节点的最长路径的节点数；最小深度是从根节点到最近的叶子节点的最短路径的节点数，如下图所示。

　　解题思路分析：采用按层遍历的方式，每遍历一轮层级加1；当在某一层遍历到第1个没有左右子节点的叶子节点时，此时记录的层级是此树的最小深度；当在某一层的所有节点均没有后续子节点时，此时记录的层级是此树的最大深度，求二叉树的最大深度和最小深度的算法图解如下图所示。

　　程序代码：

　　运行结果：

　　练习２：列表[10,6,15,9,3,13,7,16,8]和[6,10,3,15,9,13,7,16,8]中的数一样，只是顺序不一样，构成二叉排序树后，用中序遍历输出的结果是不是一样的呢？最小深度和最大深度是不是一样呢？编写程序验证你的推断。

　　求二叉树中任意两个节点之间的最低公共祖先

　　传入二叉树中两个节点的值，求两个节点之间最低的公共祖先，如下图所示。

　　解题思路分析：由于二叉排序树的左树小，右树大，因此共同祖先必然是在它们之间。从根节点开始，找到第一个在它们之间的节点才可能是共同祖先。然后在左子树中找到a、b中的最小值节点，在右子树中找到a、b中的最大值节点，这样就说明这个节点确实是共同祖先。

　　程序代码：

　　运行结果：

　　练习３：如果2个节点的最低共同祖先与另外一个节点的最低共同祖先是这3个节点的最低共同祖先。由[10,6,15,9,3,13,7,16,8,2,5,4,14,19]构成的二叉排序树，编程求2,5,8的最低共同祖先。

　　学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：

Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。

更多课程请打开“学思营”同步网站：

http://www.5xstar.com/doc.html

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社