Leetcode 114. Flatten Binary Tree to Linked List

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

For example, Given

The flattened tree should look like:

s思路： 1. 看起来，是先访问中间，然后左边，最后右边。又是一个PRe-order. 2. 用recursive当然最简单。左边flatten，右边flatten,然后让root指向flatten后的左边，让flatten的左边的尾节点指向flatten后的右边。也就是说，在flatten过程中需要知道头节点和尾节点的指针！ 3. 由于要得到左子树和右子树的开头结尾，所以需要开头结尾指针从底层得到给上层使用，因此用reference！ 4. 用iterative很有意思，用stack很麻烦，反而不用stack的morris比较方便快捷，由于是pre-order：根左右，传统的方法，访问了左边还要回到根以便访问右边，所以必须用stack;morris则是换一个角度来看问题，把树临时改变一下结构：在每个root时，先找到左子树的最右节点，然后让这个最右节点指向右子树的第一个节点，这就方便了，等访问完左子树，就直接访问右节点！ z正常情况下使用morris，还需要在建立这个辅助的连接后拆除这个连接以还原树的本来结构，但这道题就要求改变树的结构，所以说，用morris刚刚好！