21-25题

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]