思路：递归即可

    1. # 给定一个二叉树，原地将它展开为一个单链表。 
    2. # 
    3. #  
    4. # 
    5. #  例如，给定二叉树 
    6. # 
    7. #      1
    8. #    / \
    9. #   2   5
    10. #  / \   \
    11. # 3   4   6 
    12. # 
    13. #  将其展开为： 
    14. # 
    15. #  1
    16. #  \
    17. #   2
    18. #    \
    19. #     3
    20. #      \
    21. #       4
    22. #        \
    23. #         5
    24. #          \
    25. #           6 
    26. #  Related Topics 树 深度优先搜索 
    27. #  👍 695 👎 0
    30. # leetcode submit region begin(Prohibit modification and deletion)
    31. # Definition for a binary tree node.
    32. # class TreeNode(object):
    33. #     def __init__(self, val=0, left=None, right=None):
    34. #         self.val = val
    35. #         self.left = left
    36. #         self.right = right
    37. class Solution(object):
    38.     def flatten(self, root):
    39.         """
    40.         :type root: TreeNode
    41.         :rtype: None Do not return anything, modify root in-place instead.
    42.         """
    44.         def dfs(node):
    45.             if not node:
    46.                 return node
    47.             dfs(node.left)
    48.             dfs(node.right)
    49.             tmp = node.right
    50.             node.right = node.left
    51.             node.left = None
    52.             while node.right:
    53.                 node = node.right
    54.             node.right = tmp
    56.         return dfs(root)
    59. # leetcode submit region end(Prohibit modification and deletion)
    60. class TreeNode(object):
    61.     def __init__(self, val=0, left=None, right=None):
    62.         self.val = val
    63.         self.left = left
    64.         self.right = right