Problem #114: Flatten Binary Tree to Linked List

Intuition & Strategy Breakdown

Use reverse postorder traversal (Right -> Left -> Root) or Morris traversal. Flatten tree into a single right-pointing linked list.

Python Solution

def flatten(root):
    curr = root
    while curr:
        if curr.left:
            # Find the rightmost node in the left subtree
            pre = curr.left
            while pre.right:
                pre = pre.right
            
            # Attach current's right to the rightmost's right
            pre.right = curr.right
            # Move left subtree to the right
            curr.right = curr.left
            curr.left = None
        # Move to the next node
        curr = curr.right

Java Solution

class Solution {
    public void flatten(TreeNode root) {
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left != null) {
                TreeNode pre = curr.left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                pre.right = curr.right;
                curr.right = curr.left;
                curr.left = null;
            }
            curr = curr.right;
        }
    }
}