专栏首页用户6811391的专栏Python 刷题笔记:二叉树专题二

Python 刷题笔记:二叉树专题二

昨天接触了二叉树中的前中后三序遍历的代码实现,今天来看剩下的那种层序遍历。

题目一

「第 102 题:二叉树的层序遍历」

难度:中等

给你一个二叉树,请你返回其按 层序遍历 得到的节点值。(即逐层地,从左到右访问所有节点)。

「示例:」

二叉树:[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果:

[
  [3],
  [9,20],
  [15,7]
]

题目分析

看其输出格式,是将二叉树每层的节点放到单独的列表中,而代码输入的是 root 根节点,要通过 root.left 取左子节点、root.right 取其右节点。那么可以每次都提取同一层的节点记录在同一列表中,遍历列表、取列表中节点的子节点,继续将结果放入同一列表中,直到最后一层。

代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
       # 如果根节点非空,其放入层列表中
        if root!=None:
            level = [root]
       # 若根节点空,保持列表为空,最终直接返回
        else:
            level = []
       # 用来记录结果的列表
        result = []
       # 当层列表非空时
        while level:
          # 将层列表中的节点值组成列表存入结果中
            result.append([ item.val for item in level if item!=None])
          # 新的层列表
            new_level = []
          # 遍历当前层列表
            for node in level:
             # 如果左子节点非空
                if node.left!=None:
                # 将左子节点加入到新的层列表中
                    new_level.append(node.left)
             # 同理处理右子节点
                if node.right!=None:
                    new_level.append(node.right)
          # 将新的子节点赋给层列表,带入下次循环
            level = new_level
       # 返回结果列表
        return result

提交测试表现:

执行用时 : 48 ms, 在所有 Python3 提交中击败了 37.30% 的用户
内存消耗 : 14.1 MB, 在所有 Python3 提交中击败了 7.14% 的用户

原本想参考题解优化的,后来发现题解中提到的“广度优先搜索”方法下的代码逻辑与我们的代码基本相同。

❝广度优先搜索算法(英语:Breadth-First Search,缩写为BFS),又译作宽度优先搜索,或横向优先搜索,是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。 维基百科-广度优先搜索 ❞

挺开心的,可以独立做出二叉树的题了!

题目二

「面试题 检查平衡性」

难度:简单

实现一个函数,检查二叉树是否平衡。在这个问题中,平衡树的定义如下:任意一个节点,其两棵子树的高度差不超过 1。

示例 1:
给定二叉树 [3,9,20,null,null,15,7]
    3
   / \
  9  20
    /  \
   15   7
返回 true 。

示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
      1
     / \
    2   2
   / \
  3   3
 / \
4   4
返回 false 。

#来源:力扣(LeetCode)
#链接:https://leetcode-cn.com/problems/check-balance-lcci

题目分析

这虽然标着个简单题,考虑半天没有头绪,想着如果通过层序遍历这二叉树,给每层节点记录高度,但越想就越复杂了。学习下题解里的优秀解法吧!

这里直接贴代码来学习:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # 这里相当于定义了个全局变量
    def __init__(self):
        self.flag = True
    def isBalanced(self, root: TreeNode) -> bool:
    # 定义获取节点高度的函数,之后递归调用
        def isb(root):
          # 空节点,返回高度 0
            if not root:
                return 0
            # 由左子树可计算出的高度=左子树高度+1
            l = isb(root.left) + 1
            # 由右子树计算的高度 = 右子树高度+1
            r =  isb(root.right) + 1
            # 若左右子树高度差大于1
            if abs(l-r)>1:
              # 将全局的平衡状态改为 False
                self.flag = False
            # 返回左右计算的最大高度      
            return max(l,r)
        # 由根节点开始执行函数
        isb(root)
        # 返回最终的平衡状态
        return self.flag

#作者:skyyou-dang
#链接:https://leetcode-cn.com/problems/check-balance-lcci/solution/she-zhi-yi-ge-bian-liang-bao-cun-xia-mou-ge-jie-di/

原以为会是比较简单直接的计算高度方法,没想到用到了递归,以及通过 __init__ 中定义初始属性实现了全局变量的作用。我尝试着去掉这个 __init__ 中对 flag 的定义与使用,换成函数内的变量会麻烦很多。对类、方法、属性这些通过题目也有比较多接触,之后也要专门系统整理下相关内容。

这个解法思路,赞,多消化消化。

题目三

「第 226 题:翻转二叉树」

难度:简单

翻转一棵二叉树。

示例 1:
输入:
     4
   /   \
  2     7
 / \   / \
1   3 6   9

示例 2:
输出:
     4
   /   \
  7     2
 / \   / \
9   6 3   1

#来源:力扣(LeetCode)
#链接:https://leetcode-cn.com/problems/invert-binary-tree

题目分析

「解法一:」

看到这题,首先想到的还是遍历每个节点,然后将其左右子节点对调就可以了。遍历的过程还是用我们第一题里设计的层级遍历,应该就能一遍过。

代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
       # 空节点单独处理下        
        if root ==None:
            return None
    # 层列表
        level = [root]
       # 层列表不为空,循环
        while level:
          # 装子节点的新列表
            new_level = []
            # 遍历层列表中的节点
            for item in level:
              # 对调左右子节点位置
                item.left,item.right = item.right,item.left
                # 若左子节点非空
                if item.left:
                  # 加入到新列表中
                    new_level.append(item.left)
                # 新列表添加非空右子节点
                if item.right:
                    new_level.append(item.right)
            # 层列表更新为新记录的子节点列表,进入下一层循环
            level = new_level
        # 对调完所有的,返回根节点
        return root

提交测试表现:

执行用时 : 36 ms, 在所有 Python3 提交中击败了 80.20% 的用户
内存消耗 : 13.7 MB, 在所有 Python3 提交中击败了 5.26% 的用户

「解法二」

难得发现一道可以自己壮着胆子用递归的题目,既然是要翻转二叉树,那么翻转子树完全可以通过递归调用自身来实现,翻转完两子树,再将两子节点翻转即可!

代码一气呵成:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
       # 空节点返回 None
        if root==None:
            return None
       # 递归翻转左子树
        self.invertTree(root.left)
       # 递归翻转右子树
        self.invertTree(root.right)
       # 交换左右子节点
        root.left, root.right = root.right,root.left
       # 返回根节点
        return root

提交测试表现:

执行用时 : 40 ms, 在所有 Python3 提交中击败了 61.62% 的用户
内存消耗 : 13.7 MB, 在所有 Python3 提交中击败了 5.26% 的用户

结论

今天遇到的二叉树题目,要么是基于层序遍历,要么是基于递归实现,做起来也有豁然开朗的感觉。

二叉树初接触可能会不知所云,慢慢摸索规律还是挺有意思的。加上昨天,我们练习了五道 LeetCode 关于二叉树的题目(外加一道面试题目),明天二叉树先告一段落、继续换个专题练习。

本文分享自微信公众号 - TTTEED(TEDxPY),作者:TED

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python 刷题笔记:广度优先搜索专题

    昨天看过了简单题汇聚的深度优先搜索专题,今天来体验下简单级别的广度优先搜索专题。老样子,先熟悉下术语概念:

    TTTEED
  • 翻转链表与数组去重—— LeetCode 第 25、26 题记

    昨天转载了篇关于递归算法的解读文,很佩服可以透彻掌握算法又能信手拈来做讲解。反思之前我刷题的记录,像是记流水账、没太多营养,所以希望有时间的话能继续深挖下算法,...

    TTTEED
  • 这才是面试官想听的:详解「递归」正确的打开方式

    递归,是一个非常重要的概念,也是面试中非常喜欢考的。因为它不但能考察一个程序员的算法功底,还能很好的考察对时间空间复杂度的理解和分析。

    TTTEED
  • 详解Python中的浅复制与深复制

    列表对象的copy()方法返回列表的浅复制。所谓浅复制,是指生产一个新的列表,并且把原列表中所有元素的引用都复制到新列表中。如果原列表中只包含整数、实数、复数等...

    Python小屋屋主
  • 学习Python编程须知的5 个 Python 特性

    很多人认为,lambda、map和filter是初学者应该最先掌握的 Python“技巧”,但由于它们缺乏灵活性,实际上,它们在大多数情况下并不是非常有用。

    加米谷大数据
  • 每个程序员都该知道的五大定律

    定律 - 或称法则,可以指导我们并让我们在同伴的错误中学习。这篇文章中,我将介绍我每次设计或实现软件时出现在我脑海的五大定律。其中有些和开发有关,有些和系统组织...

    企鹅号小编
  • 个性化推荐最佳实践

    image.png 个性化推荐最佳实践 一、基本概念 网络营销解决方案提供商Questus公司的调查显示,在选择网络购物的消费者中,32%的人认为浏览体验非常...

    首席架构师智库
  • H3C RIP

    [R3]ip route-static 0.0.0.0 0.0.0.0 NULL 0

    py3study
  • 欢迎挑战!14个数据分析和机器学习项目!附数据集

    对于那些对数据,数据分析或数据科学感兴趣的人,提供一份可以利用业余时间完成的数据科学项目清单,一共14个!

    统计学家
  • 隔离太无聊?每天一个数据科学项目,数据集都准备好了!

    首先,我想向所有的护士,医生,超市员工,公共管理人员以及其他冒着生命危险为我们服务的人致敬。

    大数据文摘

扫码关注云+社区

领取腾讯云代金券