二叉树的层次遍历是指一层一层地遍历二叉树，并按照每层为一个列表返回，实例如下，
图1. 二叉树的层次遍历
二叉树1的层次遍历结果为：[[1] [2, 3] [4, 5, 6, 7]]；
二叉树2的层次遍历结果为：[[1], [2, 3], [6, 7]]
层次遍历的特点为不按照左右节点优先遍历某 一遍，而是先将同一层的元素先全部遍历结束。因此，层次遍历的算法考虑先将某一层的节点存储如列表，等访问完该层后，再访问该层所有的左右节点。算法步骤如下，
初始化：首先定义访问列表to_visit为下一层需要访问的所有节点，初始化为只含有根节点的列表；定义结果列表r：
（1）遍历变量to_visit，
（2）当前节点的值存入结果；
（3）访问列表to_visit的值更新append为当前列表中所有左右节点；
直到to_visit为空列表[]时，返回结果。
1.2 逆二叉树逆二叉树为将二叉树的左右枝反转。以图1为例，将其进行逆转之后结果如下，
图2. 二叉树逆转
在进行二叉树的遍历时，每个节点的左右都要交换，直到节点为空，因此，从该思路来看，该逆转的思路是递归算法。算法如下，
（1）初始化，从根部节点开始；
（2）若是当前节点有右半部分，那么其新的左半部分=右半部分；否则左半部分为空；右节点为根节点递归逆转；
（3）若是当前节点有左半部分，那么其新的右半部分=左半部分；否则右半部分为空；左节点为根节点递归逆转。
直到节点为空为止。
在这个里面有一个细节值得注意，在右半部分非空的时候，不能直接将节点的左半部分赋值为右半部分，需要暂时存储起来，等到判断完左半部分之后才能处理右半部分的赋值。
一定注意！！！：在Python中，object1=object，在修改object1的时候，object也会随之改变，因其地址为相同的，指向同一地址。在Python内置的数据类型，tmp=a.clone()，可以避免在tmp发生改变时改变a的值。但是自己定义的类就不能这样操作啦~~~~参考，让一个对象=另一个对象，修改一个对象的值，如何不影响另一个的值_VR_wangkr的博客-CSDN博客_java对象赋值给另一个对象怎么才能不变成一个对象
2. 代码 2.1 二叉树的层次遍历LeetCode107，力扣
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
图3. 层数遍历示例
代码如下，
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def set_left(self, left):
self.left = left
def set_right(self, right):
self.right = right
class Solution(object):
def levelOrderBottom(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
r = []
if root == None:
return []
current = [root]
while current != []:
tmp = []
r_tmp = []
for node in current:
r_tmp.append(node.val)
if node.left != None:
tmp.append(node.left)
if node.right != None:
tmp.append(node.right)
r.append(r_tmp)
current = tmp
r.reverse()
return r
if __name__ == '__main__':
root = [1, 2, 3]
node1 = TreeNode(3)
node2 = TreeNode(9)
node3 = TreeNode(20)
node4 = TreeNode(15)
node5 = TreeNode(7)
node1.set_left(node2)
node1.set_right(node3)
node3.set_left(node4)
node3.set_right(node5)
sol = Solution()
# r = sol.preorderTraversal(node1)
r = sol.levelOrderBottom(node1)
r1 = sol.invertTree(node1)
print(r)
2.2 逆二叉树
LeetCode226，力扣
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
图4. 逆二叉树示例
代码如下，
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if root == None:
return
r = root
flag = 0
if root.right != None:
flag = 1
tmp = self.invertTree(root.right)
if root.left != None:
root.right = self.invertTree(root.left)
else:
root.right = None
if flag == 1:
root.left = tmp
else:
root.left = None
return r
