Leetcode 1609. Even Odd Tree (python)

题目

解法1：BFS

本质上是个level order traversal再加一些判断即可，BFS版本的解法中需要额外的空间

class Solution:def isEvenOddTree(self, root: TreeNode) -> bool:q = collections.deque()q.append(root)levels = [[root.val]]while q:_len = len(q)curr_level = []for i in range(_len):node = q.popleft()if node.left:curr_level.append(node.left.val)q.append(node.left)if node.right:curr_level.append(node.right.val)q.append(node.right)levels.append(curr_level)levels = levels[:-1]#print(levels)for i,level in enumerate(levels):print(level)if i%2==0:# if len(level)%2==0:# return Falseif len(level)==1:if level[0]%2==0:return Falsefor j in range(1,len(level)):if level[j]<=level[j-1]:return Falseif level[j]%2==0:return Falseif i%2!=0:if len(level)==1:if level[0]%2!=0:return Falsefor j in range(1,len(level)):if level[j]>=level[j-1]:return Falseif level[j]%2!=0:return Falsereturn True

解法2：DFS

这里用DFS做level order traversal的时候用到了两个技巧：

• 首先要保证相应的层上升序或者降序，只需要maintain现在看到的最右边的数字即可
• 不需要预先得到树的深度或者层数，只需要在进入recursion的时候判断一下当前的depth和我存放值的list的长度然后决定操作即可

class Solution:def isEvenOddTree(self, root: TreeNode) -> bool:def dfs(node,depth):nonlocal ansif not node:returnif depth>len(values)-1:if depth%2==0: values.append(float('-inf'))else:values.append(float('inf'))if depth%2==0:if values[depth]>=node.val or node.val%2==0:ans = Falseif depth%2!=0:if values[depth]<=node.val or node.val%2!=0:ans = Falsevalues[depth] = node.valdfs(node.left,depth+1)dfs(node.right,depth+1)ans = Truevalues = []dfs(root,0)return ans

follow

这边顺便看一下树的level order traversal，之前在用DFS解的时候是这么写的：

class Solution:def levelOrder(self, root: TreeNode) -> List[List[int]]:def get_depth(node):return 1+max(get_depth(node.left),get_depth(node.right)) if node else 0def dfs(node,depth):if not node:returnans[depth].append(node.val)dfs(node.left,depth+1)dfs(node.right,depth+1)depth = get_depth(root)ans = []for i in range(depth):ans.append([])print(ans)dfs(root,0)return ans

这边需要预先知道树的深度，然后需要预先开辟空数组存放答案，但是按照前面说的技巧，可以不用预先知道深度

class Solution:def levelOrder(self, root: TreeNode) -> List[List[int]]:def dfs(node,depth):if not node:returnif len(ans)-1<depth:ans.append([])ans[depth].append(node.val)dfs(node.left,depth+1)dfs(node.right,depth+1)ans = []dfs(root,0)return ans