题解 | #牛群的树形结构展开#

• 题目考察的知识点 : 序遍历，递归
• 题目解答方法的文字分析：

1. 对于一个根节点 root，将其左子树和右子树分别展开成单链表；
2. 将左子树插入到根节点和右子树之间；
3. 返回新的根节点。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @return TreeNode类
#
class Solution:
    def flattenTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None

        left = root.left
        right = root.right

        root.left = None
        root.right = self.flattenTree(left)

        cur = root
        while cur.right:
            cur = cur.right
        cur.right = self.flattenTree(right)

        return root