将二叉树扁平化为链表的递归解

Question

问题描述链接:扁二叉树到链表有:

# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
def flatten(self, root):
"""
:type root: TreeNode
:rtype: None Do not return anything, modify root in-place instead.
"""

解决方案是:

class Solution:
def flattenTree(self, node):
# Handle the null scenario
if not node:
return None
# For a leaf node, we simply return the
# node as is.
if not node.left and not node.right:
return node
# Recursively flatten the left subtree
leftTail = self.flattenTree(node.left)
# Recursively flatten the right subtree
rightTail = self.flattenTree(node.right)
# If there was a left subtree, we shuffle the connections
# around so that there is nothing on the left side
# anymore.
if leftTail:
leftTail.right = node.right
node.right = node.left
node.left = None
# We need to return the "rightmost" node after we are
# done wiring the new connections.
return rightTail if rightTail else leftTail
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
self.flattenTree(root)

我看不懂这段代码:

if leftTail:
leftTail.right = node.right (step 1)
node.right = node.left      (step 2)
node.left = None

例如，二叉树输入为[1, 2, 3]，则步骤1后的leftTail为:[2, null, 3]。我天真地以为在第二步之后，树变成了[1, null, 3]，但令我惊讶的是，它变成了:[1,null,2,null,3]。

Answer 1

假设您的示例中有树[1, 2, 3]:

1 (node)
/ 
2   3

让我们检查一下每一步都完成了什么:

if leftTail:
leftTail.right = node.right (step 1)
node.right = node.left      (step 2)
node.left = None            (step 3)

步骤1:

1 (node)
/ 
2   3

3 (same as above)

步骤2:

1 (node)
/ 
2   2 (same as left)
   
3   3

步骤3:

1 (node)

2

3

因此，实现了[1, null, 2, null, 3]。