leetcode 114. Flatten Binary Tree to Linked List (python)

攜手創作,共同成長！這是我參與「掘金日新計劃 · 8 月更文挑戰」的第4天,點擊查看活動詳情

描述

Given the root of a binary tree, flatten the tree into a "linked list":

• The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
• The "linked list" should be in the same order as a pre-order traversal of the binary tree.

Example 1:

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]
復制代碼

Example 2:

Input: root = []
Output: []
復制代碼

Example 3:

Input: root = [0]
Output: [0]
復制代碼

Note:

The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100
復制代碼

解析

根據題意,給定二叉樹的根 root ,Compress the nodes in the tree into a linked list：

• “鏈表”應該使用相同的 TreeNode 類,where the right child pointer points to the next node in the list,The left child pointer is always null.
• “鏈表”should be in the same order as the preorder traversal of the binary tree.

The easiest way to solve this problem is to use it directly DFS 進行前序遍歷,find the nodes,Then splicing them into the title in order“鏈表”.

時間復雜度為 O(N) ,空間復雜度為 O(N) .

解答

class Solution(object):
def flatten(self, root):
""" :type root: TreeNode :rtype: None Do not return anything, modify root in-place instead. """
nodes = []
def dfs(root):
if root:
nodes.append(root)
dfs(root.left)
dfs(root.right)
dfs(root)
N = len(nodes)
for i in range(1, N):
pre, cur = nodes[i-1], nodes[i]
pre.left = None
pre.right = cur
復制代碼

運行結果

Runtime: 37 ms, faster than 49.14% of Python online submissions for Flatten Binary Tree to Linked List.
Memory Usage: 14.2 MB, less than 73.92% of Python online submissions for Flatten Binary Tree to Linked List.
復制代碼

解析

The requirement for us in the title is to use O(1) space complexity to solve this problem,That is, we cannot use the extra space,The entire binary tree can only be manipulated by changing the pointer“鏈表”,通過觀察我們發現,In fact, when the left subtree of a node is empty,則不需要進行操作,If the left subtree of a node is not empty,Then the last node in the preorder traversal in the left subtree is the rightmost leaf node in the left subtree,We only need to transfer the right subtree of the node to the rightmost leaf node of the left subtree“鏈表”轉換.

時間復雜度為 O(N) ,空間復雜度為O (1) .

解答

class Solution(object):
def flatten(self, root):
""" :type root: TreeNode :rtype: None Do not return anything, modify root in-place instead. """
while root:
if root.left:
pre = nxt = root.left
while pre.right:
pre = pre.right
pre.right = root.right
root.left = None
root.right = nxt
root = root.right
復制代碼

運行結果

Runtime: 31 ms, faster than 68.59% of Python online submissions for Flatten Binary Tree to Linked List.
Memory Usage: 14.3 MB, less than 73.92% of Python online submissions for Flatten Binary Tree to Linked List.
復制代碼

原題鏈接

leetcode.com/problems/fl…

您的支持是我最大的動力