LeetCode-Python-114. ツリーをチェーンテーブルに展開

ツリーを指定し、チェーンテーブルとして展開します.
例えば、所与のツリー

    1
   / \
  2   5
 / \   \
3   4   6

次のように展開します.

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

第一の考え方:
その場にいなければ、配列記録の前順に遍歴して、もう1つずつ載せておけばいいのですが・・・
2つ目の考え方:
再帰.まず左右のサブツリーをまっすぐにして、それから右のサブツリーをバックアップして、まっすぐにした左のサブツリーを右のサブツリーの位置に移して、左のサブツリーを空にして、
今の右の木の末尾を見つけて、まっすぐにした元の右の木をつなぎます.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        
        if not root or (not root.left and not root.right):
            return root
        
        #        
        self.flatten(root.left)
        self.flatten(root.right)
        
        tmp = root.right #           
        
        root.right = root.left #           
        root.left = None #        
        while(root.right): #            node
            root = root.right
        root.right = tmp #