Description

Flatten a binary tree to a fake "linked list" in pre-order traversal.

Here we use the right pointer in TreeNode as the next pointer in ListNode.

Notice

Don't forget to mark the left child of each node to null. Or you will get Time Limit Exceeded or Memory Limit Exceeded.

Example

              1
               \
     1          2
    / \          \
   2   5    =     3
  / \   \          \
 3   4   6          4
                     \
                      5
                       \
                        6

Solution

1. Traverse: pre-order的顺序是root-left-right，因此装入stack的顺序是right-left-root
2. Divide- Conquer: result linkedlist 中 root.right = root.left, root左子树的result linkedlist的最末点 = root.right，最末点=root右子树的result linkedlist的最末点。因此，我们只需一个建立linkedlist并返回不为最末点的helper function

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */


public class Solution {
    /*
     * @param root: a TreeNode, the root of the binary tree
     * @return: 
     */
    public void flatten(TreeNode root) {
        // write your code here
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        TreeNode next;
        TreeNode cur = null;
        while (!stack.isEmpty()) {
            next = stack.pop();
            if (next.right != null) {
                stack.push(next.right);
            }
            if (next.left != null) {
                stack.push(next.left);
            }

            if (cur != null) {
                cur.right = next;
                cur = next;
            } else {
                cur = next;
            }
            cur.left = null;
        }
    }
}