-
Notifications
You must be signed in to change notification settings - Fork 0
LC 0114 [M] Flatten Binary Tree to Linked List
Code with Senpai edited this page Feb 1, 2022
·
7 revisions
preorder is: root - left - right
so this reverse preorder: right - left - root
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
def __init__(self):
self.prev = None
def flatten(self, root):
if not root: return None
# right
self.flatten(root.right)
# left
self.flatten(root.left)
# root
root.right = self.prev
root.left = None
self.prev = root
iterative
class Solution:
def flatten(self, root: TreeNode) -> None:
curr = root
while curr:
if curr.left != None:
p = curr.left
while p.right != None:
p = p.right
p.right = curr.right
curr.right = curr.left
curr.left = None
curr = curr.right
footer