Flatten a binary tree to a fake “linked list” in pre-order traversal.
Here we use the right pointer in TreeNode as the next pointer in ListNode.
Don’t forget to mark the left child of each node to
null. Or you will get Time Limit Exceeded or Memory Limit Exceeded.
1 \ 1 2 / \ \ 2 5 => 3 / \ \ \ 3 4 6 4 \ 5 \ 6
This problem can be easily implemented using an recursive algorithm. We first call
flatten() on the left and right subtrees. The base case of this method would be either when the tree node is null or the node is a leaf node.
Once we have flattened the child subtrees, we can assign the flattened last subtree to be the right subtree. We find the end of the flattened left tree and connect the flattened right subtree to that.