21、从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
二叉树的广度优先遍历，比较简单。可以直接用队列实现。但题目要求每一层输出一行，还是直接用列表吧。
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
all_node = [[root.val]]
cur_node = [root]
while cur_node:
cur_next = []
for i in cur_node:
if i.left:
cur_next.append(i.left)
if i.right:
cur_next.append(i.right)
if cur_next:
cur_node = cur_next
cur_next = [j.val for j in cur_next]
all_node.append(cur_next)
else:
break
return all_node
22、之字型打印二叉树
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
只要在上一题的基础上改一下，偶数行翻转一下列表就可以了。
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
all_node = [[root.val]]
cur_node = [root]
cur_flag = 1
while cur_node:
cur_next = []
for i in cur_node:
if i.left:
cur_next.append(i.left)
if i.right:
cur_next.append(i.right)
if cur_next:
cur_flag += 1
cur_node = cur_next
cur_next = [j.val for j in cur_next]
if cur_flag %2 == 0:
all_node.append(cur_next[::-1])
else:
all_node.append(cur_next)
else:
break
return all_node
23、序列化和反序列化二叉树
开始看到题目有点懵，没太懂题目的意思，然后去leetcode里看了一下，虽然在leetcode里难度是困难，但其实挺简单的，就利用广度优先遍历一遍，把值为None的节点也记录下来。就可以根据这个序列来反序列化二叉树了。
感觉写反序列化的时候有点麻烦，后来看了别人的答案，在序列化的时候直接用先序遍历，反序列化起来比较方便。
class Solution:
def Serialize(self, root):
# write code here
def doit(node):
if node:
vals.append(str(node.val))
doit(node.left)
doit(node.right)
else:
vals.append('#')
vals = []
doit(root)
return ' '.join(vals)
def Deserialize(self, s):
# write code here
def doit():
val = next(vals)
if val == '#':
return None
node = TreeNode(int(val))
node.left = doit()
node.right = doit()
return node
vals = iter(s.split())
return doit()
---------------------
作者：ep_mashiro
来源：CSDN
原文：https://blog.csdn.net/tinkle181129/article/details/79326023?utm_source=copy
版权声明：本文为博主原创文章，转载请附上博文链接！
24、数据流中的中位数
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
添加数据列表和链表都能做到。考虑到时间复杂度，链表的插入操作的时间复杂度低于列表，但是找中位数时，两者的时间复杂度都是O(n)级别，leetcode困难的题应该不会这么简单 ，想了一会也没想到其它的比较快的办法。看了一下别人的答案，用两个堆实现。不太会，以后再更新
25、二叉平衡树的第K大节点
二叉平衡树的中序遍历的结果就是一个排序数组，只要将中序遍历结果记录在列表，就可以得到第K大的节点了。
class Solution(object):
def __init__(self):
self.vals = []
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
def midTravel(root):
if not root:
return None
midTravel(root.left)
self.vals.append(root.val)
midTravel(root.right)
midTravel(root)
return self.vals[k-1]
