45. Invert Binary Tree
🎯 leetcode - 226. Invert Binary Tree
🤔 私の答え
📌 質問する
📌 一つ.簡潔な解答
🤔 私の答え
📌 質問する
- 파이썬 알고리즘 인터뷰 45번 문제
📌 名前の日付2020.02.16
📌 試行回数5 try
💡 Codeclass Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
queue = [root]
while queue:
node = queue.pop(0)
if node:
node.left, node.right = node.right, node.left
queue.append(node.left)
queue.append(node.right)
return root
💡 トラブルシューティング方法- BFS를 이용해서 이진 트리의 상위 노드부터 뒤집었다.
- 뒤집는 과정을 나타내면 다음과 같다.
1. 처음 상태
4
/ \
2 7
/ \ / \
1 3 6 9
2. node = 4
4
/ \
7 2 << node.left, node.right = node.right, node.left
/ \ / \
6 9 1 3
3. node = 7, 2
4
/ \
7 2
/ \ / \
9 6 3 1 << node.left, node.right = node.right, node.left
3. node = 9, 6, 3, 1 (*node.left, node.right가 모두 None이라서 바뀌는 것이 없음)
4
/ \
7 2
/ \ / \
9 6 3 1
💡 新知-
答えを間違える理由✔ if node: 조건을 추가해주지 않아서 에러가 생겼다.
- 위의 코드에서는 리프노드 이후의 None 값까지 queue에 담는다.
None에 대해서는 node.left, node.right를 구할 수 없다.
따라서 무조건 if node: 라는 조건문을 추가해주어야 한다~!
😉 別の解釈📌 一つ.簡潔な解答
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
root.left, root.right = \
self.invertTree(root.right), self.invertTree(root.left)
return root
💡 トラブルシューティング方法- 재귀를 통해 리프노드까지 내려가서 백트래킹 하면서 스왑하는 상향 방식
- 위의 BFS를 통한 풀이와 스왑 방향이 반대이다. (리프부터 스왑 ~ 루트로 이동)
📌 二.DFS+繰返し構造class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
stack = [root]
while stack:
node = stack.pop()
if node:
node.left, node.right = node.right, node.left
stack.append(node.left)
stack.append(node.right)
return root
💡 トラブルシューティング方法- queue.pop(0)을 stack.pop()으로 수정하여
LIFO를 따르는 stack으로 바꿈으로써 DFS로 구현했다.
- DFS의 pop 순서(4>2>1>3>7>6>9)대로 차례대로 left, right를 스왑한다.
Reference
この問題について(45. Invert Binary Tree), 我々は、より多くの情報をここで見つけました https://velog.io/@eunseokim/45.-Invert-Binary-Treeテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol