Misc
114. Flatten Binary Tree to Linked List
- Sentinel + Preorder
- Recursive with Tail Return
- Iterative Stack
- Morris-like (Space Optimized)
Interactive Visualization
Analysis
- Python
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
def rec(node):
nonlocal curr
if node:
curr.right = node
curr = curr.right
left, right = curr.left, curr.right
curr.left = curr.right = None
rec(left)
rec(right)
sentinel = curr = TreeNode(None)
rec(root)
return sentinel.right
Interactive Visualization
Analysis
- Python
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
def rec(node):
if node:
if not node.left and not node.right:
return node
left = rec(node.left)
right = rec(node.right)
if left:
left.right = node.right
node.right = node.left
node.left = None
return right if right else left
return rec(root)
Interactive Visualization
Analysis
- Python
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
stack = [(root, False)]
sentinel = curr = TreeNode(None)
while stack:
node, visited = stack.pop()
if node:
if not visited:
stack.append((node.right, False)) if node.right else None
stack.append((node.left, False)) if node.left else None
stack.append((node, True))
else:
curr.right = node
curr = curr.right
node.left = node.right = None
return sentinel.right
Interactive Visualization
Analysis
- Python
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
curr = root
while curr:
if not curr.left:
curr = curr.right
else:
# find inorder predecessor
node = curr
pred = curr.left
while pred.right:
pred = pred.right
pred.right = curr.right
curr = curr.left
node.right = node.left
node.left = None
234. Palindrome Linked List
- Array Approach
- Recursive Approach
- Two Pointers with Reversal (Optimal)
Analysis
- Python
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
arr = []
while head:
arr.append(head.val)
head = head.next
return arr == arr[::-1]
Analysis
- Python
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
def rec(node):
nonlocal front
if node:
if not rec(node.next):
return False
if front.val != node.val:
return False
front = front.next
return True
front = head
return rec(head)
Analysis
- Python
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
def reverse(head: Optional[ListNode]) -> Optional[ListNode]:
"""Abdul Bari's solution"""
front, mid, back = head, None, None
while front:
front, mid, back = front.next, front, mid
mid.next = back
return mid
def middleNode(head: Optional[ListNode]) -> Optional[ListNode]:
mid_prev = None
slow = fast = head
while fast and fast.next:
mid_prev = slow
slow, fast = slow.next, fast.next.next
return slow, mid_prev
middle_node, mid_prev = middleNode(head)
last_node = reverse(middle_node)
result = True
a, b = head, last_node
while a and b:
if a.val != b.val:
result = False
break
a, b = a.next, b.next
if mid_prev:
mid_prev.next = reverse(last_node)
return result