LeetCode 솔루션 분류
[7/27] 114. Flatten Binary Tree to Linked List
본문
Medium
7874473Add to ListShareGiven 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)?Accepted
642,352
Submissions
1,088,613
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
Runtime: 57 ms, faster than 53.19% of Python3 online submissions for Flatten Binary Tree to Linked List.
Memory Usage: 15.3 MB, less than 47.67% of Python3 online submissions for Flatten Binary Tree to Linked List.
Memory Usage: 15.3 MB, less than 47.67% of Python3 online submissions for Flatten Binary Tree to Linked List.
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
if not root: return
if not root.left and not root.right: return root
if root.left:
left_leaf = self.flatten(root.left)
right_tmp = root.right
root.right = root.left
root.left = None
left_leaf.right= right_tmp
if root.right:
return self.flatten(root.right)
return left_leaf