平衡二叉树的判定

　　平衡二叉树的所有节点左右子树最大深度之差（平衡因子）的绝对值不超过1。递归算法逻辑：用临时变量记录节点左右子树的深度，空指针保持原值；左右子树深度之差的绝对值大于1时判定该树不是平衡二叉树；否则返回左右子树深度中的最大值。

　　程序代码：

　　运行结果：

　　练习１：运用平衡二叉树降维法原理，把列表[1,6,8,2,3,4,5,7,9,10]改成可以构建平衡二叉树的列表，代替上例中的列表，验证。

　　平衡二叉树转化

　　为了能应用节点数平衡法或降维法，这里的平衡二叉树都是用节点数平衡因子衡量的。

　　算法逻辑：

　　(1)更新二叉树所有节点的节点数平衡因子：采用递归法，分别算出左子树和右子树的节点数，然后用它们的差作为节点数平衡因子，返回它们的和加1（节点本身计数）。

　　(2)节点数平衡法调整：对于节点数平衡因子，底层的调整不影响上层的节点数平衡因子，因此采用递归法，先调整节点的左右子树，再调整节点本身，操作过程一律不更新length属性。

　　程序代码：

　　运行结果：

　　练习２：把一个二叉树中序遍历后可得到一个顺序列表，用这个列表，采用降维法也可以生成平衡二叉树，编程转化，原数据：

[4,1,10,-3,0,2,5,9,-1,3,6,7,11]。

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

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

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

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

参考资料：

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