Skip to content

114 flatten binary tree to linked list

114. Flatten Binary Tree to Linked List

题目: https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

难度:

Medium

这道题看了hint,说每个node的右节点都是相应先序遍历中它的下一个节点。 所以我的思路是先把先序遍历的node顺序搞出来,然后对于这里面的每一个节点,只需要做两个操作: 1. node.left = None 2. node.right = 相应先序遍历中node的下一个节点

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        def preorder(root):
            res = []
            if not root:
                return res
            res.append(root)
            if root.left: 
                res.extend(preorder(root.left))
            if root.right:
                res.extend(preorder(root.right))
            return res
        if not root:
            return
        node_order = preorder(root)
        for i in range(len(node_order)-1):
            node_order[i].left = None
            node_order[i].right = node_order[i+1]
        node_order[-1].left = None
        node_order[-1].right = None

beat 40.67%

另外一种解法: 1. copy the left and right subtree 2. then cut root’s left subtree 3. do DFS 4. left and right has been flattened and connect them left and right back to the root

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        if not root:
            return
        left_node = root.left
        right_node = root.right
        root.left = None
        self.flatten(left_node)
        self.flatten(right_node)
        if left_node:
            root.right = left_node
            while left_node.right:
                left_node = left_node.right
            left_node.right = right_node

beat 32.18%



回到顶部