102. Flatten Binary Tree to Linked List

For each node with a left child, find the rightmost node of the left subtree and attach the right subtree there, then move left subtree to right.

Approach

1. For each node, if it has a left child: a. Find the rightmost node of the left subtree. b. Attach the current node's right subtree to that rightmost node. c. Move the left subtree to the right. d. Set left to null.
2. Move to the right child.

Complexity

• Time: O(n)
• Space: O(1)

class Solution {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) { this.val = val; }
    }

    public TreeNode flatten(TreeNode root) {
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left != null) {
                TreeNode rightmost = curr.left;
                while (rightmost.right != null) {
                    rightmost = rightmost.right;
                }
                rightmost.right = curr.right;
                curr.right = curr.left;
                curr.left = null;
            }
            curr = curr.right;
        }
        return root;
    }
}