Description
Given the root of a binary tree, flatten the tree into a "linked list":
- The "linked list" should use the same
TreeNodeclass where therightchild pointer points to the next node in the list and theleftchild pointer is alwaysnull. - The "linked list" should be in the same order as a pre-order traversal of the binary tree.
Example 1:
Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [0]
Output: [0]
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]. 100 <= Node.val <= 100
Solutions
Solution 1
Intuition
Code
public void flatten(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> nodes = new Stack<>();
nodes.push(root);
while (!nodes.isEmpty()) {
TreeNode node = nodes.pop();
if (node.right != null) {
nodes.push(node.right);
}
if (node.left != null) {
nodes.push(node.left);
}
node.left = null;
if (!nodes.isEmpty()) {
node.right = nodes.peek();
}
}
}
Complexity
- Time: O(n^2)
- Space: O(n)
Solution 2
Intuition
Code
public void flatten(TreeNode root) {
if (root == null) {
return;
}
TreeNode left = root.left, right = root.right;
root.left = null;
root.right = left;
flatten(left);
flatten(right);
TreeNode cur = root;
while (cur.right != null) {
cur = cur.right;
}
cur.right = right;
}
Complexity
- Time: O(N^2)
- Space: O(N)
Solution 3
public void flatten(TreeNode root) {
TreeNode curr = root;
while (curr != null) {
if (curr.left != null) {
TreeNode prev = curr.left;
while (prev.right != null) {
prev = prev.right;
}
prev.right = curr.right;
curr.right = curr.left;
curr.left = null;
}
curr = curr.right;
}
}
Top comments (0)