動機
preorder的tree threading
Problem
Given the root
of a binary tree, flatten the tree into a linked list:
- The linked list should use the same
TreeNode
class where theright
child pointer points to the next node in the list and theleft
child pointer is alwaysnull
. - The linked list should be in the same order as a pre-order traversal of the binary tree.
Example 1:
Input: root = [1,2,5,3,4,null,6]Output: [1,null,2,null,3,null,4,null,5,null,6]
Example 2:
Input: root = []Output: []
Example 3:
Input: root = [0]Output: [0]
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]
. -100 <= Node.val <= 100
Follow up: Can you flatten the tree in-place (with
O(1)
extra space)?Sol
class Solution:
def flatten(self, root: TreeNode) -> None:
def pre(root,prev):
if root:
originRight = root.right
pro = pre(root.left, root)
ret = pre(originRight, pro)
if prev:
prev.left, prev.right = None, root
# 目前最大的node
if not pro and not ret:
return root
elif not pro or not ret:
return [x for x in [pro,ret] if x][0]
else:
return ret
else:
return None
pre(root, None)