21、從上到下按層打印二叉樹，同一層結點從左至右輸出胡桨。每一層輸出一行。

二叉樹的廣度優(yōu)先遍歷计雌，比較簡單∶钓可以直接用隊列實現白粉。但題目要求每一層輸出一行，還是直接用列表吧鼠渺。

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里難度是困難，但其實挺簡單的雁芙，就利用廣度優(yōu)先遍歷一遍轧膘，把值為None的節(jié)點也記錄下來。就可以根據這個序列來反序列化二叉樹了兔甘。
感覺寫反序列化的時候有點麻煩谎碍，后來看了別人的答案，在序列化的時候直接用先序遍歷洞焙，反序列化起來比較方便蟆淀。

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 
版權聲明：本文為博主原創(chuàng)文章，轉載請附上博文鏈接澡匪！

24熔任、數據流中的中位數
設計一個支持以下兩種操作的數據結構：

void addNum(int num) - 從數據流中添加一個整數到數據結構中。
double findMedian() - 返回目前所有元素的中位數仙蛉。

添加數據列表和鏈表都能做到笋敞。考慮到時間復雜度荠瘪，鏈表的插入操作的時間復雜度低于列表夯巷，但是找中位數時赛惩，兩者的時間復雜度都是O(n)級別，leetcode困難的題應該不會這么簡單 趁餐，想了一會也沒想到其它的比較快的辦法喷兼。看了一下別人的答案后雷，用兩個堆實現季惯。不太會，以后再更新

25臀突、二叉平衡樹的第K大節(jié)點
二叉平衡樹的中序遍歷的結果就是一個排序數組勉抓，只要將中序遍歷結果記錄在列表，就可以得到第K大的節(jié)點了候学。

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]