Flatten Binary Tree to Linked List

Question

Given a binary tree, flatten it to a linked list in-place.

Solution

想了一下，最後有解出來，只是效率不夠好。基本概念是將樹分成 left, right，然後分別再去 flatten

public void flatten(TreeNode root) {
        if (root == null) return;

        TreeNode left = root.left;
        TreeNode right = root.right;

        root.left = null;

        flatten(left);
        flatten(right);

        root.right = left;
        TreeNode cur = root;
        while (cur.right != null) cur = cur.right;
        cur.right = right;
    }

也可以參考一下神人所寫出來的遞迴

private TreeNode prev = null;

public void flatten(TreeNode root) {
    if (root == null)
        return;
    flatten(root.right);
    flatten(root.left);
    root.right = prev;
    root.left = null;
    prev = root;
}