這是問題描述的鏈接： Flatten Binary Tree to Linked List有：
# 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]，那么leftTail在第 1 步之后將是：[2, null, 3]。我天真的想法是在第 2 步之后，樹變成[1, null, 3]了，但令我驚訝的是，它變成了：[1,null,2,null,3].
uj5u.com熱心網友回復：
假設您的示例帶有樹[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]就達到了。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/496375.html