Level, Height, Depth¶
Depth¶
104. Maximum Depth of Binary Tree (Easy)¶
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
def recursion(node):
nonlocal cur_level, level_sum_count
if node:
level_sum_count[cur_level][0] += node.val
level_sum_count[cur_level][1] += 1
cur_level += 1
recursion(node.left) if node.left else None
recursion(node.right) if node.right else None
cur_level -= 1
level_sum_count = collections.defaultdict(lambda: [0, 0])
cur_level = 1
recursion(root)
return [total / count for total, count in level_sum_count.values()]
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
stack = [(root, 1)]
level_sum_count = collections.defaultdict(lambda: [0, 0])
while stack:
node, level = stack.pop()
if node:
level_sum_count[level][0] += node.val
level_sum_count[level][1] += 1
stack.append((node.right, level + 1)) if node.right else None
stack.append((node.left, level + 1)) if node.left else None
return [total / count for total, count in level_sum_count.values()]
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
queue = [root]
next_queue = []
level_avgs = []
while queue:
level_sum = 0
nodes_count = 0
while queue:
node = queue.pop(0)
if node:
level_sum += node.val
nodes_count += 1
next_queue.append(node.left) if node.left else None
next_queue.append(node.right) if node.right else None
queue = next_queue
next_queue = []
level_avgs.append(level_sum / nodes_count)
return level_avgs
Height¶
Tree: Height of a Binary Tree (E)¶
def height(root):
def maxHeight(root):
if not root:
return 0
else:
left_depth = maxHeight(root.left)
right_depth = maxHeight(root.right)
return max(left_depth, right_depth) + 1
return maxHeight(root) - 1
Level¶
637. Average of Levels in Binary Tree (Easy)¶
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
else:
left_depth = self.maxDepth(root.left)
right_depth = self.maxDepth(root.right)
return max(left_depth, right_depth) + 1
def maxDepth(self, root: Optional[TreeNode]) -> int:
stack = [(root, 1)]
max_depth = 0
while stack:
node, level = stack.pop()
if node:
max_depth = max(max_depth, level)
stack.append((node.right, level + 1))
stack.append((node.left, level + 1))
return max_depth
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
queue = [root]
next_queue = []
level = 0
while queue:
while queue:
node = queue.pop(0)
if node:
next_queue.append(node.left) if node.left else None
next_queue.append(node.right) if node.right else None
queue = next_queue
next_queue = []
level += 1
return level
1302. Deepest Leaves Sum (Medium)¶
def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
def recursion(root):
nonlocal max_depth, cur_depth
if root:
cur_depth += 1
max_depth = max(max_depth, cur_depth)
hm[cur_depth] += root.val
recursion(root.left)
recursion(root.right)
cur_depth -= 1
hm = defaultdict(int)
cur_depth = max_depth = 0
recursion(root)
return hm[max_depth]
def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
stack = [(root, 1)]
hm = defaultdict(int)
max_depth = 0
while stack:
node, level = stack.pop()
if node:
max_depth = max(max_depth, level)
hm[level] += node.val
stack.append((node.right, level + 1))
stack.append((node.left, level + 1))
return hm[max_depth]
def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
queue = [root]
next_queue = []
level_sum = 0
while queue:
level_sum = 0
while queue:
node = queue.pop(0)
if node:
level_sum += node.val
next_queue.append(node.left) if node.left else None
next_queue.append(node.right) if node.right else None
queue = next_queue
next_queue = []
return level_sum
513. Find Bottom Left Tree Value (Medium)¶
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
def recursion(node, level):
nonlocal leftmost_node, leftmost_node_level
if node:
if leftmost_node_level < level:
leftmost_node = node
leftmost_node_level = level
recursion(node.left, level + 1) if node.left else None
recursion(node.right, level + 1) if node.right else None
leftmost_node = None
leftmost_node_level = -1
recursion(root, 1)
return leftmost_node.val
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
stack = [(root, 1)]
leftmost_node = None
leftmost_node_level = -1
while stack:
node, level = stack.pop()
if node:
if leftmost_node_level < level:
leftmost_node = node
leftmost_node_level = level
stack.append((node.right, level + 1)) if node.right else None
stack.append((node.left, level + 1)) if node.left else None
return leftmost_node.val
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
queue = [root]
next_queue = []
leftmost_node = None
while queue:
leftmost_node = queue[0]
while queue:
node = queue.pop(0)
if node:
next_queue.append(node.left) if node.left else None
next_queue.append(node.right) if node.right else None
queue = next_queue
next_queue = []
return leftmost_node.val
1609. Even Odd Tree (Medium)¶
def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
isOdd = lambda i: i % 2 == 1
isEven = lambda i: i % 2 == 0
def recursion(node, level):
if node:
if not (isOdd if isEven(level) else isEven)(node.val):
return False
if level not in hm:
hm[level] = node.val
else:
if isEven(level) and hm[level] >= node.val:
return False
elif isOdd(level) and hm[level] <= node.val:
return False
hm[level] = node.val
left = recursion(node.left, level + 1)
right = recursion(node.right, level + 1)
return left and right
return True
hm = {}
ans = recursion(root, 0)
return ans
def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
isOdd = lambda i: i % 2 == 1
isEven = lambda i: i % 2 == 0
stack = [(root, 0)]
hm = {}
while stack:
node, level = stack.pop()
if node:
if not (isOdd if isEven(level) else isEven)(node.val):
return False
if level not in hm:
hm[level] = node.val
else:
if isEven(level) and hm[level] >= node.val:
return False
elif isOdd(level) and hm[level] <= node.val:
return False
hm[level] = node.val
stack.append((node.right, level + 1))
stack.append((node.left, level + 1))
return True
def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
isOdd = lambda i: i % 2 == 1
isEven = lambda i: i % 2 == 0
queue = [root]
next_queue = []
level = 0
prev = None
while queue:
nprint(*queue)
while queue:
node = queue.pop(0)
if node:
if not (isOdd if isEven(level) else isEven)(node.val):
return False
if not prev:
prev = node.val
else:
if isEven(level) and prev >= node.val:
return False
elif isOdd(level) and prev <= node.val:
return False
prev = node.val
next_queue.append(node.left) if node.left else None
next_queue.append(node.right) if node.right else None
queue = next_queue
next_queue = []
prev = None
level += 1
return True
Categorize¶
543. Diameter of Binary Tree (Easy)¶
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
def recursion(root):
if root:
nonlocal diameter
left_height = recursion(root.left)
right_height = recursion(root.right)
diameter = max(diameter, left_height + right_height)
return max(left_height, right_height) + 1
return 0
diameter = 0
recursion(root)
return diameter
563. Binary Tree Tilt (Easy)¶
def findTilt(self, root: Optional[TreeNode]) -> int:
def recursion(node):
if node:
nonlocal total
left_sum = recursion(node.left)
right_sum = recursion(node.right)
total += abs(left_sum - right_sum)
return left_sum + right_sum + node.val
return 0
total = 0
recursion(root)
return total
366. Find Leaves of Binary Tree (Medium)¶
def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:
def recursion(node):
if node:
left_height = recursion(node.left)
right_height = recursion(node.right)
height = max(left_height, right_height) + 1
hm[height].append(node.val)
return height
return 0
hm = defaultdict(list)
recursion(root)
return list(hm.values())