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%
