总得思路就是把左子树的尾巴返回出来接到右子树的头,然后再把左子树的头赋值给父节点的右子树.
难点在于怎么取出来左子树的尾巴.
这里和最短求和路径相似,都是从上往下遍历,但是从下往上处理.这里还少了判断求和路径的值,只是把该分路径下的尾巴节点返回. 代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
if root is None:
return
def find_tail(node):
if node is None:
return
left_tail = find_tail(node.left)
right_tail = find_tail(node.right)
if left_tail:
if right_tail:
left_tail.right = node.right
node.right = node.left
node.left = None
return right_tail
else:
node.right = node.left
node.left = None
return left_tail
if right_tail:
return right_tail
return node
find_tail(root)
|