114. Flatten Binary Tree to Linked List

114. Flatten Binary Tree to Linked List

题目:
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

难度:

Medium

有hint，又是玩DFS的preorder，用的loop，也不算很聪明的算法

用stack来放node，每次把pop出来的node左边变成null，把它的right指向下一个pop出来的node，也就是为嘛有prev，然后root处特殊处理一下

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        if root == None:
            return
        s = []
        s.append(root)
        prev = root
        while s:
            node = s.pop()
            if node.right:
                s.append(node.right)
            if node.left:
                s.append(node.left)
            node.left = None
            if node == root:
                continue
            else:
                prev.right = node
                prev = node