Binary Tree¶
Table of Contents¶
- 298. Binary Tree Longest Consecutive Sequence (Medium) 👑
- 549. Binary Tree Longest Consecutive Sequence II (Medium) 👑
- 250. Count Univalue Subtrees (Medium) 👑
- 1120. Maximum Average Subtree (Medium) 👑
- 545. Boundary of Binary Tree (Medium) 👑
- 366. Find Leaves of Binary Tree (Medium) 👑
- 314. Binary Tree Vertical Order Traversal (Medium) 👑
298. Binary Tree Longest Consecutive Sequence 👑¶
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# Binary Tree
def longestConsecutive(root: Optional[TreeNode]) -> int:
res = 0
def dfs(node):
if not node:
return 0
left, right = dfs(node.left), dfs(node.right)
cur = 1
if node.left and node.left.val == (node.val + 1):
cur = max(cur, left + 1)
if node.right and node.right.val == (node.val + 1):
cur = max(cur, right + 1)
nonlocal res
res = max(res, cur)
return cur
dfs(root)
return res
if __name__ == "__main__":
root = build([1, 3, 2, 4, None, None, None, 5])
print(root)
# 1
# / \
# 3 2
# /
# 4
# /
# 5
print(longestConsecutive(root)) # 3
549. Binary Tree Longest Consecutive Sequence II 👑¶
250. Count Univalue Subtrees 👑¶
1120. Maximum Average Subtree 👑¶
545. Boundary of Binary Tree 👑¶
366. Find Leaves of Binary Tree 👑¶
from collections import defaultdict
from typing import List, Optional
from binarytree import Node as TreeNode
from binarytree import build
def findLeaves(root: Optional[TreeNode]) -> List[List[int]]:
depths = defaultdict(list)
def dfs(node):
if not node:
return 0
l, r = dfs(node.left), dfs(node.right)
depth = 1 + max(l, r)
depths[depth].append(node.val)
return depth
dfs(root)
return [i for i in depths.values()]
if __name__ == "__main__":
root = build([1, 2, 3, 4, 5])
print(root)
# __1
# / \
# 2 3
# / \
# 4 5
print(findLeaves(root)) # [[4, 5, 3], [2], [1]]