Dare2Solve
To flatten the tree, we need to rearrange its nodes such that the left subtree of each node is moved to the right, and the original right subtree is appended to the end of this new right subtree. The transformation should maintain the order of nodes as they would appear in a pre-order traversal.
curr
.runner
).curr
to the rightmost node in the left subtree.None
.curr
to the right child.O(n), where n is the number of nodes in the tree. Each node is visited once.
O(1), as the solution uses a constant amount of extra space.
class Solution
{
public:
void flatten(TreeNode* root) {
TreeNode* curr = root;
while (curr) {
if (curr->left) {
TreeNode* runner = curr->left;
while (runner->right) {
runner = runner->right;
}
runner->right = curr->right;
curr->right = curr->left;
curr->left = nullptr;
}
curr = curr->right;
}
}
};
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
curr = root
while curr:
if curr.left:
runner = curr.left
while runner.right:
runner = runner.right
runner.right = curr.right
curr.right = curr.left
curr.left = None
curr = curr.right
class Solution {
public void flatten(TreeNode root) {
TreeNode curr = root;
while (curr != null) {
if (curr.left != null) {
TreeNode runner = curr.left;
while (runner.right != null) {
runner = runner.right;
}
runner.right = curr.right;
curr.right = curr.left;
curr.left = null;
}
curr = curr.right;
}
}
}
var flatten = function (root)
{
let curr = root
while (curr)
{
if (curr.left) {
let runner = curr.left
while (runner.right) runner = runner.right
runner.right = curr.right, curr.right = curr.left, curr.left = null
}
curr = curr.right
}
};