453. Flatten Binary Tree to Link

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.

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

Example 1:

Input:{1,2,5,3,4,#,6}

Output：{1,#,2,#,3,#,4,#,5,#,6}

Explanation：

    1

    / \

  2  5

  / \  \

3  4  6

1

\

2

  \

  3

    \

    4

      \

      5

        \

        6

Example 2:

Input:{1}

Output:{1}

Explanation：

        1

        1

Challenge

Do it in-place without any extra memory.

思路:

分治法， 先假设左子树已经排好了，右子树也排好了， 在根节点只需要将根节点和左子树排好的结果连起来， 再将左子树排好的结果的最后一个和右子树排好的结果连起来， 为了能顺利的链接， 就需要知道左子树排好顺序后的最后一个节点，去获得最后一个节点又有两种方法，一种是单独建一个函数去返回节点， 另一种是用一个全局变量去记录最后一个节点， 前者相对好理解一点。我自己想的答案就没有这么结构化，需要在每次得到左子树结果之后去遍历到最后一个节点，所以放在这里只做记录用。

代码：

我自己的

用答案写的：

用全局变量的