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

public class Solution {
    public void flatten(TreeNode root) {
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left != null) {
                // 找到左子樹(shù)的最右節(jié)點(diǎn)
                TreeNode prev = curr.left;
                while (prev.right != null) {
                    prev = prev.right;
                }
                // 將右子樹(shù)接到最右節(jié)點(diǎn)
                prev.right = curr.right;
                // 將左子樹(shù)移到右側(cè)，并清空左側(cè)
                curr.right = curr.left;
                curr.left = null;
            }
            // 處理下一個(gè)節(jié)點(diǎn)
            curr = curr.right;
        }
    }
}

import java.util.ArrayList;
import java.util.List;

class Solution {
    public void flatten(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) return;
        List<TreeNode> result = new ArrayList<>();
        preOrder(root, result);
        // 重建鏈表
        for (int i = 0; i < result.size() - 1; i++) {
            TreeNode prev = result.get(i);
            TreeNode cur = result.get(i + 1);
            prev.left = null;
            prev.right = cur;
        }
    }

    private void preOrder(TreeNode root, List<TreeNode> result) {
        if (root == null) return;
        result.add(root);
        preOrder(root.left, result);
        preOrder(root.right, result);
    }
}

private void preOrder(TreeNode root, List<TreeNode> result) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;
    while (node != null || !stack.isEmpty()) {
        while (node != null) {
            result.add(node);
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        node = node.right;
    }
}