Return the preorder, inorder, or postorder traversal of a binary tree root.
def inorderTraversal(root):
return [x.val for x in dfs(root)]Binary Tree Preorder Traversal
def preorderTraversal(root):
return [x.val for x in dfs(root, 'preorder')]Binary Tree Postorder Traversal
def postorderTraversal(root):
return [x.val for x in dfs(root, 'postorder')]def findTarget(root, k):
nums = [x.val for x in dfs(root)]
if len(nums) >= 2:
enum = dict()
for i, x in enumerate(nums):
if x in enum:
return True
else:
enum[k - x] = i
return FalseAll Elements in Two Binary Search Trees
import itertools
def getAllElements(root1, root2):
reverse_inorder = lambda x: [y.val for y in dfs(x)][::-1]
lists = [[], reverse_inorder(root1), reverse_inorder(root2)]
while lists[1] and lists[2]:
lists[0] += [sorted(lists[1:], key = lambda z: z[-1])[0].pop()]
return itertools.chain(*lists)Apply the function func(x, L, R) to a tree binary tree node root where x is the root, L is the output of func applied to root.left', and R is the output of func applied to root.right. Set the base case to func(x = None) = base.
def maxDepth(root):
return memoize(root, 0, lambda x, L, R: max(L, R) + 1)def isBalanced(root):
depth = memoize(root, 0, lambda x, L, R: max(L, R) + 1, True)
return memoize(root, True,
lambda x, L, R: all([abs(depth[x.left] - depth[x.right]) <= 1, L, R])
)def minDepth(root):
return memoize(root, 0, lambda x, L, R: (L or R) + 1)def maxPathSum(root):
return max(memoize(root, [-float('inf'), -float('inf')],
lambda x, L, R: [x.val + max(L[0], R[0], 0),
max(L + R + [x.val + L[0] + R[0]])
])
)def sumNumbers(root):
return memoize(root, 0, lambda x, L, R: x.val + (L + R)*10)def binaryTreePaths(root):
concatenate = lambda x, value: [str(x.val) + '->' + y for y in value]
return memoize(root, [],
lambda x, L, R: [str(x.val)]
if x.left == x.right == None
else concatenate(x, L) + concatenate(x, R)
)def rob(root):
return max(memoize(root, (0, 0),
lambda x, L, R: (L[1] + R[1] + x.val, max(L) + max(R))
))def sumOfLeftLeaves(root):
def func(x, L, R):
s = R
if x.left:
if x.left.left == x.left.right == None:
s += x.left.val
else:
s += L
return s
return memoize(root, 0, func)import statistics
def findFrequentTreeSum(root):
subtree_sum = memoize(root, 0, lambda x, L, R: x.val + L + R, True)
del subtree_sum[None]
return statistics.multimode(subtree_sum.values())def diameterOfBinaryTree(root):
depth = memoize(root, 0, lambda x, L, R: max(L, R) + 1, True)
return memoize(root, 0,
lambda x, L, R: max(depth[x.left] + depth[x.right], L, R)
)def findTilt(root):
subtree_sum = memoize(root, 0, lambda x, L, R: x.val + L + R, True)
return memoize(root, 0,
lambda x, L, R: abs(subtree_sum[x.left] - subtree_sum[x.right]) + L + R
)Construct String from Binary Tree
def tree2str(t):
def func(x, L, R):
s = str(x.val)
if x.left:
s += parenthesize(L)
if x.right:
s += parenthesize(R)
elif x.right:
s += '()' + parenthesize(R)
return s
parenthesize = lambda y: '(' + y + ')'
return memoize(t, '()', func) if t else ''def trimBST(root, L, R):
def func(x, _L, _R):
if x.val < L:
return _R
elif x.val > R:
return _L
x.left, x.right = _L, _R
return x
return memoize(root, None, func)Second Minimum Node in a Binary Tree
def findSecondMinimumValue(root):
def func(x, L, R):
if x.left == x.right == None:
return -1
a = x.left.val if x.left.val != x.val else L
b = x.right.val if x.right.val != x.val else R
if min(a, b) > -1:
return min(a, b)
elif a > -1:
return a
else:
return b
return memoize(root, -1, func)def longestUnivaluePath(root):
def func(root, L, R):
left_same = is_same(root, root.left)
right_same = is_same(root, root.right)
return max((L + R + 2)*left_same*right_same,
(L + 1)*left_same, (R + 1)*right_same, L, R
)
is_same = lambda parent, child: bool(child and child.val == parent.val)
return memoize(root, 0, func)def pruneTree(root):
def func(x, L, R):
x.left, x.right = L, R
return None if x.val == 0 and x.left == x.right == None else x
return memoize(root, None, func)Smallest Subtree with all the Deepest Nodes
def subtreeWithAllDeepest(root):
def func(x, L, R):
if L[0] > R[0]:
return L[0] + 1, L[1]
elif L[0] < R[0]:
return R[0] + 1, R[1]
else:
return L[0] + 1, x
return memoize(root, (0, None), func)[1]def rangeSumBST(root, L, R):
def func(x, _L, _R):
if x.val < L:
return _R
elif x.val > R:
return _L
else:
return x.val + _L + _R
return memoize(root, 0, func)def isUnivalTree(root):
return memoize(root, True, lambda x, L, R: all([x.val == root.val, L, R]))Lowest Common Ancestor of Deepest Leaves
def lcaDeepestLeaves(root):
def func(x, L, R):
if L[0] > R[0]:
return L[0] + 1, L[1]
elif L[0] < R[0]:
return R[0] + 1, R[1]
else:
return L[0] + 1, x
return memoize(root, (0, None), func)[1]def sumEvenGrandparent(root):
def sum_grandchildren(x, L, R):
s = 0
if x.left:
if x.left.left:
s += x.left.left.val
if x.left.right:
s += x.left.right.val
if x.right:
if x.right.left:
s += x.right.left.val
if x.right.right:
s += x.right.right.val
return s
sum_memo = memoize(root, None, sum_grandchildren, True)
del sum_memo[None]
return sum(sum_memo[y] for y in sum_memo if y.val%2 == 0)def removeLeafNodes(root):
def func(x, L, R):
if x.left:
x.left = L
if x.right:
x.right = R
return None if x.left == x.right and x.val == target else x
return memoize(root, None, func)Maximum Product of Splitted Binary Tree
def maxProduct(root):
subtree_sum = memoize(root, 0, lambda x, L, R: x.val + L + R, True)
return max((y*(subtree_sum[root] - y))
for y in subtree_sum.values()
) % (10**9 + 7)Longest Zigzag Path in a Binary Tree
def longestZigZag(root):
return memoize(root, (-1, -1, -1),
lambda x, L, R: (L[1] + 1,
R[0] + 1,
max(L[1] + 1, R[0] + 1, L[2], R[2])
)
)[2]Return the level-order traversal of a binary tree root, row by row.
Binary Tree Level Order Traversal
def levelOrder(root):
return [[y.val for y in x] for x in level_order(root)]Binary Tree Zigzag Level Order Traversal
def zigzagLevelOrder(root):
visited = [[y.val for y in x] for x in level_order(root)]
for i in range(1, len(visited), 2):
visited[i].reverse()
return visitedBinary Tree Level Order Traversal II
def levelOrderBottom(root):
[[y.val for y in x] for x in level_order(root)[::-1]]def rightSideView(root):
return [x[-1].val for x in level_order(root)]def findBottomLeftValue(root):
return level_order(root)[-1][0].valFind Largest Value in Each Tree Row
def largestValues(root):
return [max(y.val for y in x) for x in level_order(root)]Average of Levels in Binary Tree
import statistics
def averageOfLevels(root):
return [statistics.mean(y.val for y in x) for x in level_order(root)]def deepestLeavesSum(root):
return sum(x.val for x in level_order(root)[-1])