면접 문제 37 서열화 두 갈래 트리python3 BFS+ 보조 대기열
2122 단어 Leetcode
예:
다음 두 갈래 나무를
1 /\ 2 3 /\ 4 5
"[1,2,3,null,null,4,5]"로 서열화
이 문제의 초기 코드는 다음과 같습니다.
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))이를 통해 알 수 있듯이 서열화된 두 갈래 트리의 입력은 하나의 뿌리 노드이고 출력은 하나의 문자열이다.반서열화는 문자열 입력으로 두 갈래 트리를 재구성할 수 있습니다.다음은 각각 해답을 구하겠습니다.
1. 서열화 부분
입력: 나무의 뿌리 노드;
출력:문자열.
사고의 방향
사실 이것은 32번과 매우 비슷하다: 위에서 아래로 두 갈래 트리 Python 3 광도 우선 검색
먼저 32문제 코드를 드리겠습니다.보조 대기열 + BFS 사용# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
if not root:
return []
queue = []
res = []
queue.append(root)
while queue:
# for i in queue:
node = queue[0]
queue = queue[1:]
res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if not queue:
return res
32문항과 본문을 비교해 보면 32문항을 토대로
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
if not root:
return []
queue = []
res = []
queue.append(root)
while queue:
# for i in queue:
node = queue[0]
queue = queue[1:]
res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if not queue:
return res전체적으로 본 문제는 BFS+ 보조 대기열의 방법인 계층 순으로 다룹니다.
변경된 코드는 다음과 같습니다.
코드를 자꾸 잘못 고쳐서...가서 샤워하고 내일 고치자.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode 문제풀이 노트 113.경로 총 II경로 총 II 제목 요구 사항 문제풀이 두 갈래 나무와 목표와 뿌리 노드에서 잎 노드까지의 모든 경로를 찾는 것은 목표와 같은 경로입니다. 설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다. 예: 다음과 같은 두 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
