当前位置：首页 > news >正文

114. Flatten Binary Tree to Linked List (leetcode)

news 来源：原创 2024/4/29 5:40:54

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

The flattened tree should look like:

要求是in-place的修改, 所以只能通过遍历和修改左右节点的引用来实现, 提示中说如果是前序遍历的话, 右边节点的前一个节点就是需要连接过去的目标.

照着这个思路, 需要在递归中获取的信息有: 当前节点是否是右节点, 当前节点的父节点. 然后通过处理变成一棵线性, 全部是左节点的树.

处理顺序是, 如果节点是右节点, 先把它添加为前一个节点的左节点, 然后修改父节点, 将父节点的右节点置为空.

最后将左倾树变化为目标形式.

python 代码:

 1 class Solution(object):
 2     def __init__(self):
 3         self.prev = None
 4         
 5     def flatten(self, root):
 6         """
 7         :type root: TreeNode
 8         :rtype: void Do not return anything, modify root in-place instead.
 9         """
10         self.deal(root, None, False)
11         self.moveLeftToRight(root)
12 
13     def deal(self, node, parent, isRight):
14         if not node:
15             return
16         if isRight:
17             parent.right = None
18             self.prev.left = node
19             
20         self.prev = node
21         self.deal(node.left, node, False)
22         self.deal(node.right, node, True)
23         
24     def moveLeftToRight(self, node):
25         while node:
26             left = node.left
27             node.left = None
28             node.right = left
29             node = left
30

后来翻看别人的解答时, 发现了一个很棒的方法.

思路是: reversed pre-order, 从右往左遍历, 已demo为例顺序是 6->5->4->3->2->1, 记录下前一个节点后, 将其添加为当前节点的右节点, 然后左节点为空. 递归完毕后就是一棵右倾树了.

 1 def __init__(self):
 2     self.prev = None
 3     
 4 def flatten(self, root):
 5     if not root:
 6         return None
 7     self.flatten(root.right)
 8     self.flatten(root.left)
 9     
10     root.right = self.prev
11     root.left = None
12     self.prev = root