Flatten Binary Tree to Linked List

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

For example, Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Solution:

比较难的地方就是想到prev变量的方法，如果不用prev变量会影响后面的结果。

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
        stack = [root]
        prev = None

        while stack:
            node = stack.pop()
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
            if prev == None:
                prev = node
            else:
                prev.right = node
                prev.left = None
            prev = node

Traverse;这种做法非常巧妙.
class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        self.prev = None
        self.traverse(root)
    def traverse(self, root):
        if root == None:
            return
        if self.prev:
            self.prev.left = None
            self.prev.right = root
        self.prev = root
        right = root.right #需要提前把right 指针保留，因为后续go left 方法中会使用到right 指针。
        self.traverse(root.left)
        self.traverse(right)