Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1 / \ 2 5 / \ \ 3 4 6
The flattened tree should look like:
1 \ 2 \ 3 \ 4 \ 5 \ 6
Code
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def __init__(self): self.prev = None def flatten(self, root): """ :type root: TreeNode :rtype: void Do not return anything, modify root in-place instead. """ if root is None: return self.flatten(root.right) self.flatten(root.left) # self.prev is root's left subtree's root root.right = self.prev root.left = None self.prev = root
Idea
Create a variable self.prev
, which records the current node (root
)’s left subtree’s root. Overall it utilizes a post-order traversal. The algorithm first traverses right subtree then left subtree and finally adjusts the current root’s left and right subtree.
Reference: https://discuss.leetcode.com/topic/11444/my-short-post-order-traversal-java-solution-for-share/2
Code
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def flatten(self, root): """ :type root: TreeNode :rtype: void Do not return anything, modify root in-place instead. """ while root: ln = root.left if ln is not None: # find the right-most element of the left subtree while ln.right: ln = ln.right ln.right = root.right root.right = root.left root.left = None root = root.right
Idea
Iterative way. Time complexity is O(n) since every node can be set as root
and ln
no more than once.
Reference: https://discuss.leetcode.com/topic/3995/share-my-simple-non-recursive-solution-o-1-space-complexity