python实现leetcode之114. 二叉树展开为链表

解题思路

第一步 按照先序遍历将节点收集到队列里
第二步 便利队列，然后将每个节点left设置为None，right指向下一个节点
最后一个节点除外

114. 二叉树展开为链表

代码

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        # 按照先序遍历将节点收集到队列里
        queue = []
        dft(root, queue)
        for idx, node in enumerate(queue):
            node.left = None
            if idx < len(queue)-1:
                next_node = queue[idx + 1]
                node.right = next_node
        
def dft(tree, queue):
    if not tree: return
    queue.append(tree)
    if tree.left: dft(tree.left, queue)
    if tree.right: dft(tree.right, queue)