http://www.lintcode.com/en/problem/flatten-binary-tree-to-linked-list/#

1.travese

keep a global variable to record the last node had traversed, and give a new pointer to the current right, then recursively traverse to left then right.

public class Solution {
    /**
     * @param root: a TreeNode, the root of the binary tree
     * @return: nothing
     */

    TreeNode lastNode = null;
    public void flatten(TreeNode root) {
        // write your code here
        if (root == null) {
            return;
        }

        if (lastNode != null) {
            lastNode.left = null;
            lastNode.right = root;
        }

        lastNode = root;
        TreeNode right = root.right;
        flatten(root.left);
        flatten(right);
    }
}

1. divide and conquer