Leetcode 1609. Even Odd Tree

题目解法1：BFS解法2：DFSfollow

题目

解法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 False if len(level)==1: if level[0]%2==0: return False for j in range(1,len(level)): if level[j]<=level[j-1]: return False if level[j]%2==0: return False if i%2!=0: if len(level)==1: if level[0]%2!=0: return False for j in range(1,len(level)): if level[j]>=level[j-1]: return False if level[j]%2!=0: return False return True

解法2：DFS

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

首先要保证相应的层上升序或者降序，只需要maintain现在看到的最右边的数字即可不需要预先得到树的深度或者层数，只需要在进入recursion的时候判断一下当前的depth和我存放值的list的长度然后决定操作即可 class Solution: def isEvenOddTree(self, root: TreeNode) -> bool: def dfs(node,depth): nonlocal ans if not node: return if 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 = False if depth%2!=0: if values[depth]<=node.val or node.val%2!=0: ans = False values[depth] = node.val dfs(node.left,depth+1) dfs(node.right,depth+1) ans = True values = [] 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 0 def dfs(node,depth): if not node: return ans[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: return if 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