This approach involves a recursive pre-order traversal of the tree. The idea is to recursively flatten the left and right subtrees, then append the flattened left subtree between the root and the flattened right subtree.
The steps are as follows:
This leverage the pre-order traversal principle: Root → Left → Right.
Time Complexity: O(n) where n is the number of nodes in the tree since each node is visited once.
Space Complexity: O(n) due to the recursive call stack on an unbalanced tree.
1class TreeNode {
2 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 public void flatten(TreeNode root) {
10 if (root == null) return;
11 TreeNode left = root.left;
12 TreeNode right = root.right;
13
14 root.left = null;
15 flatten(left);
16 flatten(right);
17
18 root.right = left;
19 TreeNode curr = root;
20 while (curr.right != null) {
21 curr = curr.right;
22 }
23 curr.right = right;
24 }
25}This Java solution similarly utilizes recursion to adjust the tree into a flattened linked list. It handles the left and right subtrees separately and then links them using iteration to adjust the right pointers.
This approach simplifies the recursive method by using a stack to maintain state information. By using controlled use of stack structures, we can modify the tree iteratively.
The algorithm progresses with these steps:
This achieves similar logic as recursion but without directly using the call stack by using our custom stack for maintaining traversal state.
Time Complexity: O(n) because every node is processed once.
Space Complexity: O(n), matching the worst-case stack usage when all nodes are in a single path.
1using System.Collections.Generic;
2
3public class TreeNode {
4 public int val;
5 public TreeNode left;
6 public TreeNode right;
7 public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
8 this.val = val;
9 this.left = left;
10 this.right = right;
11 }
12}
13
14public class Solution {
15 public void Flatten(TreeNode root) {
16 if (root == null) return;
17 Stack<TreeNode> stack = new Stack<TreeNode>();
18 stack.Push(root);
19
20 while (stack.Count > 0) {
21 TreeNode current = stack.Pop();
22
23 if (current.right != null) {
24 stack.Push(current.right);
25 }
26 if (current.left != null) {
27 stack.Push(current.left);
28 }
29
30 if (stack.Count > 0) {
31 current.right = stack.Peek();
32 }
33 current.left = null;
34 }
35 }
36}C# implements the iterative process with a stack. It processes nodes in such a way that the left children will always be directly converted into right children before the existing right subtree is processed.