Side Views, Two Trees¶
Side Views¶
545. Boundary of Binary Tree (Medium)¶
def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
def setLeaves(node):
nonlocal boundary
if node:
if not node.left and not node.right:
boundary.append(node.val)
setLeaves(node.left)
setLeaves(node.right)
def setLeftBoundary(node):
if node:
if not node.left and not node.right:
return
boundary.append(node.val)
setLeftBoundary(node.left)
setLeftBoundary(node.right) if not node.left else None
def setRightBoundary(node):
if node:
if not node.left and not node.right:
return
setRightBoundary(node.right)
setRightBoundary(node.left) if not node.right else None
boundary.append(node.val)
boundary = [root.val]
setLeftBoundary(root.left) if root.left else None
setLeaves(root) if root.left or root.right else None
setRightBoundary(root.right) if root.right else None
return bounda
199. Binary Tree Right Side View (Medium)¶
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
def recursion(node, level):
nonlocal hm
if node:
hm[level] = node.val
recursion(node.left, level + 1)
recursion(node.right, level + 1)
hm = {}
recursion(root, 1)
return list(hm.values())
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
stack = [(root, 1)]
hm = {}
while stack:
node, level = stack.pop()
if node:
hm[level] = node.val
stack.append((node.right, level + 1))
stack.append((node.left, level + 1))
return list(hm.values())
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
q = [root]
ans = []
while q:
mini_q = []
mini_ans = []
while q:
node = q.pop(0)
if node:
mini_ans.append(node.val)
mini_q.append(node.left) if node.left else None
mini_q.append(node.right) if node.right else None
q = mini_q
ans.append(mini_ans[-1]) if mini_ans else None
return ans
Two Trees¶
100. Same Tree (Easy)¶
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
def recursion(a, b):
if a and b and a.val == b.val:
x = recursion(a.left, b.left)
y = recursion(a.right, b.right)
return x and y
elif not a and not b:
return True
return False
return recursion(p, q)
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
stack = [(p, q)]
while stack:
a, b = stack.pop()
if a and b:
if a.val != b.val:
return False
stack.append((a.left, b.left))
stack.append((a.right, b.right))
elif a or b:
return False
return True
101. Symmetric Tree (Easy)¶
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
def recursion(left, right):
if left and right and left.val == right.val:
a = recursion(left.right, right.left)
b = recursion(left.left, right.right)
return a and b
elif not left and not right:
return True
return False
return recursion(root.left, root.right)
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
stack = [(root.left, root.right)]
while stack:
left, right = stack.pop()
if left and right:
if left.val != right.val:
return False
stack.append((left.left, right.right))
stack.append((left.right, right.left))
elif left or right:
return False
return True
1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree (Easy)¶
def getTargetCopy(
self, original: TreeNode, cloned: TreeNode, target: TreeNode
) -> TreeNode:
def recursion(a, b):
if a and b:
if a == target:
return b
return recursion(a.left, b.left) or recursion(a.right, b.right)
return recursion(original, cloned)
def getTargetCopy(
self, original: TreeNode, cloned: TreeNode, target: TreeNode
) -> TreeNode:
stack = [(original, cloned)]
while stack:
a, b = stack.pop()
if a and b:
if a == target:
return b
stack.append((a.left, b.left))
stack.append((a.right, b.right))
return None
def getTargetCopy(
self, original: TreeNode, cloned: TreeNode, target: TreeNode
) -> TreeNode:
q = [(original, cloned)]
while q:
mini_q = []
while q:
a, b = q.pop(0)
if a and b:
if a == target:
return b
mini_q.append((a.left, b.left))
mini_q.append((a.right, b.right))
q = mini_q
return None
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