114. Flatten Binary Tree to Linked List

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

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

/**
 * Iterative Solution
 *
 * Refer:
 * https://leetcode.com/problems/flatten-binary-tree-to-linked-list/discuss/37010/Share-my-simple-NON-recursive-solution-O(1)-space-complexity!
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: O(1)
 *
 * N = Number of nodes in the tree.
 */
class Solution1 {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }

        TreeNode cur = root;

        while (cur != null) {
            // If there is no left node, the current node is at correct place in the tree.
            if (cur.left != null) {

                // We are trying to find left subTree's rightmost child. This node's right child
                // will be the current right node.
                TreeNode pre = cur.left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                pre.right = cur.right;

                // Since the right subtree has been place at the right place, Left subtree can
                // move to the right now.
                cur.right = cur.left;
                cur.left = null;
            }
            cur = cur.right;
        }
    }
}

/**
 * Recursive Solution
 *
 * Refer:
 * https://leetcode.com/problems/flatten-binary-tree-to-linked-list/discuss/37010/Share-my-simple-NON-recursive-solution-O(1)-space-complexity!
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: O(Height of the tree). In worst case O(N)
 *
 * N = Number of nodes in the tree.
 */
class Solution2 {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        flattenHelper(root, null);
    }

    // head node represents the head of the solved list.
    private TreeNode flattenHelper(TreeNode node, TreeNode head) {
        if (node == null) {
            return head;
        }

        head = flattenHelper(node.right, head);
        head = flattenHelper(node.left, head);
        node.right = head;
        node.left = null;
        return node;
    }
}