Swift Leetcode Series: Flatten Binary Tree to Linked List
Swift + Binary Trees + Linked List = Leetcode 114 ✅✅✅
Flatten Binary Tree to Linked List (Leetcode 114) -
Given the root of a binary tree, flatten the tree into a "linked list". The "linked list" should use the same TreeNode…
Check the full story on The Swift Nerd blog with the link above.
root of a binary tree, flatten the tree into a “linked list”:
- The “linked list” should use the same
TreeNodeclass where the
rightchild pointer points to the next node in the list and the
leftchild pointer is always
- The “linked list” should be in the same order as a pre-order traversal of the binary tree.
Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]Input: root = 
Output: Input: root = 
- The number of nodes in the tree is in the range
-100 <= Node.val <= 100
Follow up: Can you flatten the tree in-place (with
O(1) extra space)?
We can intuitively think of a recursively approach to traverse the list in preorder approach and recursively convert the left and right subtrees as skewed trees.
After recursively solving the left and right subtrees, all we need to do is fix some pointers with respect to the room. This recursion would move bottom-up and by the time root node is processed, we are sure that we have already converted the left and right subtrees. Now keep a pointer to traverse the rightmost node in the left subtree (this is needed to connect the right subtree as tail). When we reach the terminal node in the left subtree, simply set the left subtree as root’s right and connect the original right subtree with the terminal left node’s right.
Follow Up: O(1) Space?
Follow the blog for the optimised solution.
Time = O(N)
Space = O(N) (Stack Space for recursion).