Flatten Binary Tree to Linked List
Given the root of a binary tree, flatten the tree into a "linked list": * The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the sequence and the left child pointer is always null. * The "linked list" should be in the same order as a pre-order traversal of the binary tree.
Constraints:
- The number of nodes in the tree is in the range [0, 2000].
- -100 <= Node.val <= 100
Examples:
Input: [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]
Explanation: The input represents the binary tree: 1 / \ 2 5 / \ \ 3 4 6 The output represents the flattened binary tree: 1 \n2 \n3 \n4 \n5 \n6
Solutions
Recursive Approach
This solution uses a recursive approach to flatten the binary tree. It first recursively flattens the left and right subtrees, then it finds the rightmost node in the left subtree and sets its right child to the right subtree of the root. Finally, it sets the right child of the root to the left subtree and sets the left child of the root to null.
class Solution {
public void flatten(TreeNode root) {
if (root == null) return;
flatten(root.left);
flatten(root.right);
if (root.left != null) {
TreeNode rightmost = root.left;
while (rightmost.right != null) {
rightmost = rightmost.right;
}
rightmost.right = root.right;
root.right = root.left;
root.left = null;
}
}
}Follow-up:
How would you optimize the solution if the tree is very large and we need to reduce the space complexity?
