【实验抄题策略】笨办法抄题打卡

问题：1。自己刷题进展太慢，量不够，质也起不来 2. 形成障碍后，容易被打击，心理不太舒服，容易放弃，没有成就感，久而久之就抑郁了。

暂时解决方法：

1. 每天打卡

2.试验专题抄（提高深度）与大公司面试FB题抄（提高宽度）

3. 不讲究理解，能启发多少算多少，讲解速度与数量。

4. 回头看别人的录像

10.22、2020

目标：抄30个

今日专题：二叉树

1609. Even Odd Tree

1. BFS的队列应用 2. 难点奇偶的交替更新 3. 数学最大值小值的应用 math.inf 4. 前后值大小的比较 都很tricky

[mw_shl_code=python,true]from collections import deque

class Solution:

def isEvenOddTree(self, root: TreeNode) -> bool:

q = deque()

q.append(root)



isEven = True

prev_value = -math.inf



# normal BFS or level-trasversal

while q:

level = [][br]
for _ in range(len(q)):

node = q.popleft()

level.append(node)



if node.left:

q.append(node.left)

if node.right:

q.append(node.right)

# inspect level according to conditions

for node in level:

curr_value = node.val



if isEven:

if curr_value%2 == 0 or curr_value <= prev_value:

return False

else:

if curr_value%2 != 0 or curr_value >= prev_value:

return False

prev_value = curr_value



# set up for next iteration using the opporsite flag contions

isEven = not isEven

prev_value = -math.inf if isEven else math.inf

return True[/mw_shl_code]

1600. Throne Inheritance

心得：1. 王位继承应用题 2.二叉树的dfs应用 3. 字典和列表应用

[mw_shl_code=python,true]class ThroneInheritance:

def __init__(self, kingName: str):

# taking kingname as root

self.root = kingName

# notDead will hold all the people who are alive and their level number

self.alive = {}

self.alive[kingName] = 0

# hold edges exsisting in our graph

self.edges = {self.root:[]}[br]
def birth(self, parentName: str, childName: str) -> None:

# birth --> new child so update a live

self.alive[childName] = self.alive[parentName] + 1

# add praent to child edges i nthe edges dictionary

if parentName in self.edges:

self.edges[parentName].append(childName)

if childName not in self.edges:

self.edges[childName] = [][br]
else:

if childName not in self.edges:

self.edges[childName] = [][br]
self.edges[parentName] = [childName]



def death(self, name: str) -> None:

# removing the dead people from alive map

del self.alive[name]

def getInheritanceOrder(self) -> List[str]:

hierarchy = [][br]
def dfs(cur, parent=-1):

nonlocal hierarchy

# current person available in alive then only add in hirachy

if cur in self.alive:

hierarchy.append(cur)



# traverse all the children of current node

for i in self.edges[cur]:

if i!=parent:

dfs(i,cur)

dfs(self.root)

return hierarchy[/mw_shl_code]

1530. 好叶节点对的个数

1. 先后序遍历 2. 队列里的处理逻辑还不太懂 3. 用了defaultdict 是啥？ 还要注意树高度，为了比较距离。 这题比较综合。