리트코드 / 파이썬 / 114. Flatten Binary Tree to Linked List
leetcode.com/problems/flatten-binary-tree-to-linked-list/
Flatten Binary Tree to Linked List - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
문제 풀이
주어진 Binary Tree를 오른쪽과 같이 Flatten한다.
1 1
/ \ \
2 5 2
/ \ \ \
3 4 6 3
\
4
\
5
\
6
재귀로 풀면 된다는 것을 생각해볼 수 있는데, leaf 부터 root 까지 flatten 하는 과정을 거친다.
예시를 기준으로 보면, root를 기준으로 right를 먼저 flatten하고, 그다음 left를 flatten해야하는 것을 알 수 있다.
(그래야 flatten된 오른쪽의 가지를 왼쪽에 붙여줄 수 있다.)
1 root: 6
/ \ prev: None
2 5
/ \ \
3 4 6
1 root: 5
/ \ prev: 6
2 5
/ \ \
3 4 6
1 root: 4
/ \ prev: 5
2 5 \
/ \ \ 6
3 4 6
1 root: 3
/ prev: 4
2 \
/ \ 5
3 4 \
\ 6
5
\
6
1 root: 2
/ prev: 3
2 \
/ 4
3 \
\ 5
4 \
\ 6
5
\
6
1 root: 1
/ prev: 2
2 \
\ 3
3 \
\ 4
4 \
\ 5
5 \
\ 6
6
[result]
1
\
2
\
3
\
4
\
5
\
6
소스 코드
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
prev = None
def flatten(self, root):
"""
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
:type root: TreeNode
:rtype: None Do not return anything, modify root in-place instead.
"""
if not root:
return None
self.flatten(root.right)
self.flatten(root.left)
root.right = self.prev
root.left = None
self.prev = root
'Leetcode' 카테고리의 다른 글
| [Leetcode][Python] 98. Validate Binary Search Tree (0) | 2020.10.10 |
|---|---|
| [Leetcode][Python] 91. Decode Ways (0) | 2020.10.03 |
| [Leetcode][Python] 389. Find the Difference (0) | 2020.10.02 |
| [Leetcode][Python] 80. Remove Duplicates from Sorted Array II (0) | 2020.10.02 |
| [Leetcode][Python] 229. Majority Element II (2) | 2020.09.23 |
