LeetCode 114. Flatten Binary Tree to Linked List

Question

Given the root of a binary tree, flatten the tree into a “linked list”:

• The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
• The “linked list” should be in the same order as a pre-order traversal of the binary tree.

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

• Solution1

class Solution {
    private TreeNode prev = null;

    public void flatten(TreeNode root) {
        if (root == null)
            return;
        flatten(root.right);
        flatten(root.left);
        // linked list only have 1 direction, the first node must be inserted as first
        root.right = prev;
        root.left = null;
        prev = root;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)