114 Flatten Binary Tree to Linked List

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

For example, Given

     1
    / \
   2   5
  / \   \
 3   4   6

The flattened tree should look like: 1 \ 2 \ 3 \ 4 \ 5 \ 6

Hints: If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

resources:

https://cheonhyangzhang.wordpress.com/2015/09/29/94-leetcode-java-binary-tree-inorder-traversal-medium

http://blog.csdn.net/crazy1235/article/details/51477967

http://unknown66.blogspot.com/2016/03/leetcode-114-flatten-binary-tree-to.html

pre-order(left,parent,right)

Solution1: Traversal iteratively without using stack - Morris Algorithm

No stack, no extra space needed

The key is to leverage stack and a current pointer

Algorithm:

1. Initialize current as root
2. While current is not NULL
   • If current does not have left child
     • a) Print current’s data
     • b) Go to the right, i.e., current = current->right
   • Else
     • a) Make current as right child of the rightmost node in current's left subtree
     • b) Go to this left child, i.e., current = current->left

review: Morris Traversal

https://www.gitbook.com/book/shannonhu/shannon-s-tech-notebook/edit#/edit/master/%5Bdata_structure%5D_morris_tree_traversal_algorithm.md

    public void flatten(TreeNode root) {
        TreeNode current = root;
        TreeNode prev = null;

        while (current != null) {

            if (current.left == null) {
                // left subtree is empty, move to right subtree.
                current = current.right;
            } else {
                // Traverse to the rightmost node and thread it to right subtree
                // of current node.
                prev = current.left;

                while (prev.right != null) prev = prev.right;

                prev.right = current.right;
                current.right = current.left;
                current.left = null;

                current = current.right;
            }
        }
    }