21-25题

作者: yy辰 | 来源:发表于2018-10-11 10:27 被阅读18次

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]

相关文章

  • 21-25题

    21、从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。 二叉树的广度优先遍历,比较简单。可以直接用...

  • MySQL经典50题-第21到25题

    MySQL50-7-第21-25题 本文中介绍的是第21-25题目,主要涉及的知识点是: 分组统计求和,百分比 如...

  • 2.14【每日一词】pursue

    1.Those youngster between 21-25,vulnerable to impulsive, ...

  • 读经笔记05

    读经内容:创21-25 & 太21-25 读经感悟: 耶稣进了神的殿,赶出殿里一切做买卖的人,推倒兑换银钱之人的桌...

  • 《21-25》

    《二十一》 溅花鳞水金莲绽 金莲绽于碧影间 碧影间游鱼儿戏 鱼儿戏尾浪溅花 《二十二》 独钓江雪泪已凝 静待寒山带...

  • 21-25

  • 21-25

    21 荷叶在夏天是最美丽的,画家选择画它冬天的样子。 冬天是荷叶最动人的时候。 22 有人问一个悲观主义者:“你为...

  • 8.26-9.8

    1-8 已领 8.23 9-20 已领 8.25 21-25 已领 8.26 26-36 已领 8.26 ...

  • 中文 21-25

    Lesson 21 I Don't Know Anyone. 我谁都不认识 这个宴会上的人我一个也不认识。有个陌生...

  • 诗篇21-25

    诗篇 第21篇 〔大卫的诗,交与伶长。〕 耶和华啊,王必因你的能力欢喜;因你的救恩,他的快乐何其大!他心里所愿的,...

网友评论

      本文标题:21-25题

      本文链接:https://www.haomeiwen.com/subject/zzqpaftx.html