当前位置: 首页 > 开发杂谈 >

Day 11:94. Binary Tree Inorder Traversal

今日题目

题目连结:94. Binary Tree Inorder Traversal
题目主题:Stack, Tree, Depth-First Search, Binary Tree

前一篇Preorder Traversal分享完後,这次是Inorder Traversal观念题。若没看过前一篇,还是建议先往前看过Tree的观念及Preorder Traversal会更好。


简单说说 Inorder Traversal

在DFS(Depth-First Search)中Traversal分成三种方式:

  1. Preorder
  2. Inorder
  3. Postorder

今天会用到的就是Inorder Traversal。
前一篇提到的Preorder原则是一进入节点就读这个值,而Inorder不一样的是第一次返回到节点才读这个值。假设资料是 tree = [5, 2, 6, 1, 3, null, 8]

https://ithelp.ithome.com.tw/upload/images/20210925/20141336Zw0b64sSzR.png

上图中,每个节点上面的数字是读的顺序,而红色虚线箭头就是读的方向。Inorder排出来就会是 [1, 2, 3, 5, 6, 8],Inorder读完的感觉是整棵树越左边的节点就会越先读到,换一种方式看如下图。

https://ithelp.ithome.com.tw/upload/images/20210925/20141336ELM3KLn2UY.png


题目解说

建议可以看看LeetCode原本的题目说明,这边是用我的方式说明题目,参考就好。

今天的题目,目标就是用Inorder的方式来读取树,依照这个Inorder的顺序将节点的值排到一个列表中,最後回传这个列表。

约束:

  • 树的节点总数范围在 [0, 100]
  • 100 <= Node.val <= 100

范例1

输入: root = [1,null,2,3]
输出: [1,3,2]

范例2

输入: root = []
输出: []

范例3

输入: root = [1]
输出: [1]

范例4

输入: root = [1,2]
输出: [2,1]

范例5

输入: root = [1,null,2]
输出: [1,2]

建议到这边先停下来,尝试自己解解看,若没有想法可再继续走下去。


解题的想像

文字描述

  1. 写一个递回方法,这个方法要能传入前往的节点及要完成的list。
  2. 每呼叫一次这个方法会往一个节点前进,
  3. 这个递回会一直到走到发现没有节点才会往回走。
  4. 每当左边子节点往回走,会把目前回到节点的值纪录到list中。
  5. 最终跑完所有节点会回传一份用Inorder排出来的list。

图解过程

范例:tree = [5, 2, 6, null, 8]

下图中是实际上Traversal在走的过程,实际在想像移动过程的时候,建议在最下面的节点都补虚线的节点代表走到底了。

https://ithelp.ithome.com.tw/upload/images/20210925/20141336suDWV6DEAi.png

  1. step1 从根节点进入以後,会直接走到左边最底,回来以後的红色圆,是要开始纪录到list的第一个值。
  2. step2 跟 step4 很像都是往右边子节点前进,再往下层发现左边子节点没有值,回到红色圈就是要纪录的值。
  3. step3 当右子节点走完以後会一路往上走,回到根节点,这时也是对根节点来说,是左边的子节点走完了,因此要在这个时候纪录这个根节点到list。
  4. step5 会把剩下的虚线节点走完,确认整棵树走过一次,再走回根节点结束这个Traversal。
  5. 走完step1 ~ step5以後,就会组成step6看到的list,这个list是过程中出现的红色圆一个一个组成的,也就是Inorder Traversal最後要回传的结果。

若因为没想法而走到这边,建议看完想像以後再给自己一次机会试一次。


程序码撰写

class Solution:  
    # root 要进入的节点
    # inorder_list 最终要回传的list  
    def traversal(self, root: TreeNode, inorder_list: List[int]):
        # 没有节点往回走
        if root == None: return inorder_list
        # 前往左边子节点
        inorder_list = self.traversal(root.left, inorder_list)
        # 左边子节点回来以後,将目前节点的值纪录到list中
        inorder_list.append(root.val)
        # 前往右边子节点
        inorder_list = self.traversal(root.right, inorder_list)
        return inorder_list
    
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        return self.traversal(root, [])
        

希望您今天能了解到...

  1. Inorder Traversal
  2. 94. Binary Tree Inorder Traversal的解题方法

若内容有什麽问题或建议欢迎一起交流:)
感谢您今天愿意花时间看完这篇文章~~~~

Next:145. Binary Tree Postorder Traversal


相关文章:

  • Flutter基础介绍与实作-Day25 旅游笔记的实作(6)
  • 亚马逊的超量仓储要如何解决?
  • Day 01 - 环境安装(上) WSL2 & Ubuntu Linux GUI XFCE Desktop
  • 中东电商市场的趋势分析
  • 亚马逊店铺如何赶走跟卖
  • Day30:Azure小白如何使用Azure Active Directory Identity protection管好管满
  • 影响亚马逊排名的六个因素
  • Day 2 为什麽要学Compose UI?
  • 外贸网站打造的三个关键点
  • Day 15 ( 中级 ) 无限循环画中画
  • 亚马逊卖家关于广告投放出现的问题
  • [Day 09] tinyML开胃菜Arduino IDE上桌(下)
  • 帮服务建置布署流程至 EC2
  • 马来西亚清关需要哪些资料?得多长时间?
  • [Day30] 身为产品经理的反省与再出发
  • 通过CloudFlare Partner计划使用cname接入CloudFlare免费CDN
  • 一周要闻:谷歌母公司、Facebook、亚马逊等几大互联网公司一季度财报
  • WordPress 5.7 引入函数来检查文章是否可以公开查看
  • 搬瓦工VPS优惠码/ 促销码 、最新BandwagonHost官网促销
  • 区块链是什么东西?区块链原理是什么
  • 数字人民币是什么?什么是数字人民币
  • 如何找国外网红营销?国外网红营销方法和推荐
  • VPS评测:Clouvider Limited英国VPS性能测试
  • SiteGround主机评测和推荐
  • Google:国际化网站即使有相同的英文内容也不属于重复内容
  • 什么是301重定向?如何在WordPress网站创建301重定向?
  • Vultr促销码和2020年最新优惠:Vultr注册教程和使用方法
  • 搬瓦工VPS注册购买教程 – 支付宝BandwagonHost购买方法教程
  • 虚拟信用卡是什么?虚拟信用卡安全吗?怎么用?怎么申请教程
  • WordPress 5.7.2 修复 PHPMailer 安全漏洞,请及时更新