力扣114.二叉树展开为链表（python版本）_114. 二叉树展开为链表 python

题目来源： 114.二叉树展开为链表
题目： 给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。
  
  
  思路：递归
  给 flatten 函数输入一个结点 root ，那么以 root 为根的二叉树就会被拉平成一条链表。
  如何按照题目把一颗树拉平成一条链表？以下流程：
  1、将 root 的左子树和右子树拉平。
  2、将 root 的右子树接到左子树下方，然后将整个左子树作为右子树。
  
  比较难以理解的是第一步，如何将左右子树拉平的？根据参考链接一的解释是通过 flatten 函数的定义，对 root 的左右子树递归调用flatten函数即可。（我也没太明白为什么，理解的小伙伴可以评论区一起讨论一下。。。）
  python代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        if not root:
            return 
        self.flatten(root.left)
        self.flatten(root.right)
        if root.left:
            temp = root.left
            while (temp.right):
                temp = temp.right
            temp.right = root.right
            root.right = root.left
            root.left = None
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

参考链接： 【面试高频题】将二叉树展开为链表
二叉树展开为链表(python)
【LeetCode 114】二叉树展开为链表（Python）