【LeetCode】Binary Tree

大部分会碰到的是 Binary Tree 和 Binary Search Tree。

常见错误:null pointer

指针类型的 linked list, tree, graph 们,都会有的共同错误。
前面 linked list 有提过了,
一样就是在取值(left, right, value)时多注意是否为 None。

Recursive、Iterative 都要会

基本上树的题型就是先好好掌握下面几个基础的 iterative / recursive :
144. Binary Tree Preorder Traversal
94. Binary Tree Inorder Traversal
145. Binary Tree Postorder Traversal
102. Binary Tree Level Order Traversal

然後多写其他题型,练习递回的思维:
101. Symmetric Tree
257. Binary Tree Paths
...
通常先想清楚递回,有余力就思考这题用 dfs 比较好?还是 bfs 比较好?理由和 complexity 分析。
以及尝试用 stack 和 queue 实作 iterative,以免面试的时候不让写递回。

递回时如何带值到外面 function

以 tree 题型来说,通常 Easy 就是很直观、不太需要另一个 helper function。
Medium 则通常需要 helper function,因为递回之间传递的值并不是最後需要的答案。
但不建议这样判断啦.. 先把难度遮掉,好好思考吧XD

要带值出去外层或是纪录答案,大概有 3 种方法:

  1. 放在 instance attribute
def __init__(self):
    self.answer = 0

在递回的 function 内部直接取来用
2. nonlocal
Python3 才有
如果我在 solution 里面写 inner function,会考虑用 nonlocal keyword 取用外层变数

def solution():
    res = 0
    def recursive():
        nonlocal res
        res += 1
        return blabalbla
    recursive()
    return res
  1. 如果是 list,直接传 ref,甚至不传
def solution():
    res = []
    def recursive(): 
        res.append("meow!!!")
        return blabalbla
    recursive() # 这边也可以传 res 进去,当然上面 function definition 要改
    return res 

总结

树题目重点就是递回思考,
是否能把左右子树当作ㄧ棵全新的树丢进现在的 function?
还是要另外构造 helper function?
算是千变万化,一定要多写。

有空的话看看之後出一个递回心得吧。


<<:  Day10 - 基础篇总结 ,CI/CD 的功用为何 ?

>>:  第58天~

[从0到1] C#小乳牛 练成基础程序逻辑 Day 29 - 加速器 中/英打typing games 六大推荐

免扮女装 | 游戏中超越自己 | 手速up up | 6大推荐 ...

27. 解释 CSS 的 BFC(Block Formatting Context)

Formatting Context 所有的HTML元素,在CSS里都可以视为box(盒子),在No...

[Day5] 变数&&部份所有权&&简单的回圈

不知不觉就写了 1 / 6 了,时间也过太快了。 虽然我怕之後断掉 QQ 想必读者全部都会略过这一块...

Day02 工欲善其事必先利其器

VS Code Extension外挂套件 在建立React应用程序之前,建议可先安装VS Code...

Day 29 -资料库应用小程序 菜单显示(内涵程序码)

废话不多说直接开始 我们点选菜单按钮会连结到这个表单 全域变数 string MyConnectio...