Side Views, Two Trees¶
Two Trees¶
872. Leaf-Similar Trees (Easy)¶
def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
def recursion(node):
if not node:
return
if not node.left and not node.right:
yield node.val
yield from recursion(node.left)
yield from recursion(node.right)
return list(recursion(root1)) == list(recursion(root2))
def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
def recursion(node):
if not node:
return
if not node.left and not node.right:
yield node.val
yield from recursion(node.left)
yield from recursion(node.right)
for i, j in itertools.zip_longest(recursion(root1), recursion(root2)):
if i != j:
return False
return True
def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
def get_leaves(root):
stack = [(root, False)]
while stack:
node, visited = stack.pop()
if node:
if visited:
if not node.left and not node.right:
yield node.val
else:
stack.append((node.right, False))
stack.append((node.left, False))
stack.append((node, True))
return list(get_leaves(root1)) == list(get_leaves(root2))
def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
def get_leaves(root):
stack = [(root, False)]
while stack:
node, visited = stack.pop()
if node:
if visited:
if not node.left and not node.right:
yield node.val
else:
stack.append((node.right, False))
stack.append((node.left, False))
stack.append((node, True))
for i, j in itertools.zip_longest(get_leaves(root1), get_leaves(root2)):
if i != j:
return False
return True
617. Merge Two Binary Trees (Easy)¶
def mergeTrees(
self, root1: Optional[TreeNode], root2: Optional[TreeNode]
) -> Optional[TreeNode]:
def recursion(a, b):
if a and b:
node = TreeNode(a.val + b.val)
node.left = recursion(a.left, b.left)
node.right = recursion(a.right, b.right)
elif a:
node = TreeNode(a.val)
node.left = recursion(a.left, None)
node.right = recursion(a.right, None)
elif b:
node = TreeNode(b.val)
node.left = recursion(None, b.left)
node.right = recursion(None, b.right)
else:
return None
return node
return recursion(root1, root2)
def mergeTrees(
self, root1: Optional[TreeNode], root2: Optional[TreeNode]
) -> Optional[TreeNode]:
"""https://leetcode.com/problems/merge-two-binary-trees/discuss/121170/Python-iterative"""
def getVal(node):
return node.val if node else 0
def getNextNode(node, mode):
if mode == 0:
return node.left if node else None
else:
return node.right if node else None
root = TreeNode(0)
stack = [(root1, root2, root, 0)]
while stack:
a, b, parent, mode = stack.pop()
node = node = TreeNode(getVal(a) + getVal(b)) if a or b else None
if mode == 0: # go left (0)
parent.left = node
else: # go right (1)
parent.right = node
if a or b:
stack.append((getNextNode(a, 1), getNextNode(b, 1), node, 1))
stack.append((getNextNode(a, 0), getNextNode(b, 0), node, 0))
return root.left