114. Flatten Binary Tree to Linked List

好像是三刷。

按preOrder的顺序改成一列。

当前指向preOrder的下一个就行了，但是既然是preOrder, 当前改了之后会影响后边的go deeper 进程。。

所以不妨进入下一个之后，回过头改前面的，这样需要一global prev pointer来记录上一个是啥。。

然后注意pre order是中 - 左 - 右这个顺序，在左子的时候，prev是中，就是左的parent，此时改写parent.left = null，不会影响左；还要改写parent.right = 左（就是现在所在的Node)。
改写之后，按照中左右的顺序，该右了，但是我们刚刚把parent.right给改了。。。没法遍历了，所以要提前记录到这个Node的Path..

Time: O(n)
Space: O(n) 我看有的地方说recursion的Space 是O(lgN)。。不是很理解。。

然后无非就是迭代，递归2方式。

递归

Recursion:

public class Solution {
    TreeNode prev = null;
    public void flatten(TreeNode root) {
        if (root == null) return;
        
        if (prev != null) {
            prev.right = root;
            prev.left = null;
        }
        prev = root;
        TreeNode nextRight = root.right;
        flatten(root.left);
        flatten(nextRight);
    }
}

迭代：

卧槽。。
迭代的思路完全不一样，我尝试用prev指针做递归，做不出来= =

这个迭代的思路是，每到一个root，右边不是null就把右边push到stack里。
然后，左边不是null就把左边放到右边，右边已经push进stack了，所以不会lost trace。接下来左边按要求改成null. 再go right，此时的right其实就是本来的左边。。
假如左边是NULL，说明走到底了，正确的preOrder顺序是该右边了，而右边刚刚被我们push进去了，所以pop出来作为下一个遍历的节点。此时代表遍历了最小子树的中和左，该右边了。。

Iteration:

public class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        
        TreeNode temp = root;
        TreeNode prev = null;
        Stack<TreeNode> stk = new Stack<>();
        while (!stk.isEmpty() || temp != null) {
            if (temp.right != null) {
                stk.push(temp.right);
            }
            
            if (temp.left != null) {
                temp.right = temp.left;
                temp.left = null;
                temp = temp.right;
            } else {
                if (stk.isEmpty()) return;
                temp.right = stk.pop();
                temp = temp.right;
            }
        }
        return;
    }
}

据说还有constant space的做法。。

又是Morris...do u still remember u fucked me over once when I was trying to figure out KMP, I guess taht M stands for Morris..

Morris里建立tail pointer的时候，是指回属于他的中节点(temp))，便于今后往右(temp.right)遍历。而这里我们需要的是指向preOrder的下一个，正好就是tail指回的中节点的右边(temp.right)，所以直接指向右边就行了。 (tail = > temp.right)

然后左边要换成null,换之前把他放到temp的右边。temp.left = temp.right

然后temp = temp.right；

和迭代很像，就是只通过temp.right来go deeper..

好牛逼。。

Time: O(n)
Space: O(1)

public class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        TreeNode tail = null;
        while (root != null) {
            if (root.left != null) {
                tail = root.left;
                while (tail.right != null) {
                    tail = tail.right;
                }
                tail.right = root.right;
                root.right = root.left;
                root.left = null;
                root = root.right;
            }else {
                root = root.right;
            }
        }
        return;
    }
}