트 리 데이터 구조 - 파워 브러시 트 리 문제 알 아야 할 것 (Python)
나 무 는 중요 한 데이터 구조 이 고 이 진 트 리 는 그 중의 중점 과 난점 이다. 이 진 트 리 에 관 한 기초 지식 은 독자 가 걸음 을 옮 겨 더 많은 내용 을 볼 수 있다.여기 서 우 리 는 나무의 기본 구조 가 python 에서 어떻게 구축 되 고 응용 되 는 지 에 중심 을 두 었 다.
1. 이 진 트 리 의 결 점
두 갈래 나무의 결점 에는 세 개의 실례 변수 가 있다.
모든 노드 는 예화 할 때 이 노드 의 값 을 설정 해 야 하 며, 이 노드 는 기본적으로 좌우 아이들 이 모두 None 이 므 로 할당 문 구 를 통 해 추가 해 야 합 니 다.
class TreeNode:
"""
"""
def __init__(self, x):
self.val = x #
self.left = None #
self.right = None #
2. 이 진 트 리 구축
여기 서 우 리 는 함 수 를 설계 하여 하나의 목록 을 통 해 이 진 트 리 를 구축 하고 입력 한 목록 은 이 진 트 리 의 차원 순서에 따라 각 요 소 를 제시 합 니 다. 우 리 는 이 진 트 리 의 아래 표지 에 따라 결점 간 의 대응 관 계 를 찾 습 니 다. 아래 에 i 로 표 시 된 노드 의 좌우 아이들 이 목록 에서 의 아래 표 시 는 각각 2i + 1 과 2i + 2 입 니 다.
def create_tree(nodes):
"""
:param nodes:
:return:
"""
def helper(node, i): # ，
if i < len(nodes): #
if nodes[i] in ['#', None]: # i
return None # None
else:
node = TreeNode(nodes[i]) #
node.left = helper(node.left, 2 * i + 1) # ，
node.right = helper(node.right, 2 * i + 2) # ，
return node # i
return node #
root = TreeNode(0) #
root = helper(root, 0) #
return root #
만약 에 우리 가 이 진 트 리 를 만 들 려 고 한다 면:
1
/ \
2 3
/ \ / \
4 5 6 7
우 리 는 이 함수 만 호출 하면 된다.
root = create_binary_tree([1, 2, 3, 4, 5, 6, 7])
만약 우리 가 일반 이 진 트 리 를 구축 해 야 한다 면, 예 를 들 어:
1
/ \
2 3
/ /
4 6
우 리 는 빈 잎 결점 을 None 또는 '\ #' 로 채 울 것 입 니 다. 마지막 층 의 마지막 몇 개의 결점 이 연속 적 인 빈 결점 이 라면 조작 하지 않 아 도 됩 니 다.
root = create_binary_tree([1, 2, 3, 4, None, 6])
3. 이 진 트 리 옮 겨 다 니 기
이 진 트 리 에서 흔히 볼 수 있 는 옮 겨 다 니 는 방식 은 네 가지 가 있 는데 앞 순 서 는 옮 겨 다 니 고 중간 순 서 는 옮 겨 다 니 며 뒤 순 서 는 옮 겨 다 니 며 순서 에 관 한 기초 지식 은 [이 진 트 리 의 옮 겨 다 니 기] 를 참고 할 수 있 고 모든 옮 겨 다 니 는 것 은 재 귀 와 교체 두 가지 방식 으로 이 루어 질 수 있다.
밤 을 들 어 이 진 트 리 한 그루 에 대해 우 리 는 각각 앞 순서, 중간 순서, 뒤 순서 와 층 서 인쇄 방식 을 사용 했다. 결 과 는 다음 과 같다.
1
/ \
2 3
/ \ / \
4 5 6 7
：[1, 2, 4, 5, 3, 6, 7]
：[4, 2, 5, 1, 6, 3, 7]
：[4, 5, 2, 6, 7, 3, 1]
：[1, 2, 3, 4, 5, 6, 7]
순환 실현
옮 겨 다 니 는 재 귀적 실현 은 더욱 간결 하고 이해 하기 쉬 워 야 한다. 스 택, 대기 열 등 추가 데이터 구 조 를 빌 리 지 않 아 도 된다. 앞 순서, 중간 순서 와 뒤 순서 의 옮 겨 다 니 는 순 서 는 매우 유사 한 실현 방식 이 있 고 유일한 차 이 는 뿌리 노드 와 좌우 아이들 간 의 순서 관계 에 있다.
1. 앞 순서 옮 겨 다 니 기
def pre_order(node):
"""
:param node:
:return:
"""
if not node:
return []
return [node.val] + pre_order(node.left) + pre_order(node.right)
2. 중간 순서 옮 겨 다 니 기
def in_order(node):
"""
:param node:
:return:
"""
if not node:
return []
return pre_order(node.left) + [node.val] + pre_order(node.right)
3. 후 순 옮 겨 다 니 기
def post_order(node):
"""
:param node:
:return:
"""
if not node:
return []
return pre_order(node.left) + pre_order(node.right) + [node.val]
우 리 는 상기 세 가지 옮 겨 다 니 는 방식 을 python 의 lambda 표현 식 으로 빠르게 정의 하 는 것 을 고려 할 수 있 습 니 다. 한 마디 로 함수 만 정의 할 수 있 습 니 다.
#
pre_order = lambda node: [node.val] + pre_order(node.left) + pre_order(node.right) if node else []
#
in_order = lambda node: in_order(node.left) + [node.val] + in_order(node.right) if node else []
#
post_order = lambda node: post_order(node.left) + post_order(node.right) + [node.val] if node else []
4. 층 차 를 옮 겨 다 닌 다
우 리 는 목록 을 빌려 층 차 를 옮 겨 다 녔 다.우 리 는 층 차 를 옮 겨 다 니 는 결 과 를 목록 에 포 함 된 구조 로 표시 하고 목록 의 모든 요 소 는 각 층 의 옮 겨 다 니 는 결과 이자 목록 형식 입 니 다.재 귀적 호출 시, 우 리 는 조수 함수 (helper) 를 구축 하여, 수의 한 층 의 한 노드 를 지정 한 층 의 결과 목록 에 추가 하 는 데 사용 합 니 다.
def level_order(root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
def helper(node, level):
"""
node res
:param node:
:param level:
:return:
"""
if not node: #
return #
else:
res[level-1].append(node.val) #
if len(res) == level: # ，
res.append([]) #
helper(node.left, level+1) #
helper(node.right, level+1) #
res = [[]] #
helper(root, 1) #
return res[:-1] #
반복 실현
교체 실현 은 재 귀 실현 보다 더욱 복잡 하고 교체 법 으로 이 진 트 리 의 역 사 를 실현 하려 면 대기 열 이나 스 택 등 데이터 구 조 를 빌려 야 한다.
앞 순서, 중간 순서 와 후속 적 으로 스 택 의 데이터 구 조 를 사용 해 야 합 니 다. 그들 은 똑 같은 순환 제어 조건 이 있 습 니 다. 즉, 스 택 과 현재 노드 가 모두 비어 있 을 때 순환 을 뛰 어 넘 고 순환 내부 에서 현재 노드 가 비어 있 는 지 에 대해 서도 서로 다른 조작 이 있 습 니 다.
앞 순 서 를 옮 겨 다 니 기: 현재 결산 점 은 비어 있 지 않 습 니 다. 현재 결산 점 을 현재 결산 점 값 으로 기록 하고 오른쪽 결산 점 을 창고 에 넣 습 니 다. 현재 결산 점 을 왼쪽 아이 로 업데이트 하고 현재 결산 점 이 비어 있 을 때 창고 꼭대기 결산 점 으로 업데이트 합 니 다.
중간 순서 옮 겨 다 니 기: 현재 결산 점 이 비어 있 지 않 으 면 결산 점 이 창고 에 들 어가 고 왼쪽 아이 로 업 데 이 트 됩 니 다. 현재 결산 점 이 비어 있 을 때 창고 꼭대기 결산 점 으로 업 데 이 트 됩 니 다. 현재 결산 점 값 을 기록 하고 오른쪽 아이 로 업 데 이 트 됩 니 다.
후 순 옮 겨 다 니 기: 현재 결산 점 이 비어 있 지 않 으 면 결산 점 수 치 를 기록 하고 왼쪽 아이 가 창고 에 들 어가 면 현재 결산 점 은 오른쪽 아이 로 업데이트 되 며 노드 가 비어 있 으 면 창고 꼭대기 결산 점 으로 업 데 이 트 됩 니 다.
1. 앞 순서 옮 겨 다 니 기
def pre_order(root):
"""
:param root:
:return:
"""
stack = [] #
res = [] #
cur = root #
while stack or cur: #
if cur: #
res.append(cur.val) #
stack.append(cur.right) #
cur = cur.left #
else: #
cur = stack.pop() #
return res #
2. 중간 순서 옮 겨 다 니 기
def in_order(root):
"""
:param root:
:return:
"""
stack = [] #
res = [] #
cur = root #
while stack or cur: #
if cur: #
stack.append(cur) #
cur = cur.left #
else: #
cur = stack.pop() #
res.append(cur.val) #
cur = cur.right #
return res #
3. 후 순 옮 겨 다 니 기
def post_order(root):
"""
:param root:
:return:
"""
stack = [] #
res = [] #
cur = root #
while stack or cur: #
if cur: #
res.append(cur.val) #
stack.append(cur.left) #
cur = cur.right #
else: #
cur = stack.pop() #
return res[::-1] #
4. 층 차 를 옮 겨 다 닌 다
층 차 를 옮 겨 다 니 려 면 대기 열 을 사용 해 야 합 니 다. 매번 결산 점 을 팀 에서 내 보 내 고 이 결산 점 수 치 를 기록 하 며 좌우 아 이 를 순서대로 대열 에 넣 어야 합 니 다. 대기 열 에 결산 점 이 없 을 때 까지.
def level_order(root):
if not root: #
return [] #
res = [] #
cur = root #
queue = [cur] #
while queue: #
cur = queue.pop(0) #
res.append(cur.val) #
if cur.left: #
queue.append(cur.left) #
if cur.right: #
queue.append(cur.right) #
return res #
"의" 자형 인쇄 이 진 트 리
이것 은 이 진 트 리 의 층 차 를 옮 겨 다 니 는 작업 입 니 다. 일반적인 층 차 를 옮 겨 다 니 는 것 과 달리 우 리 는 짝수 줄 이 진 트 리 의 층 결 과 를 역 순 으로 하면 됩 니 다.여기 서 여러분 에 게 이해 하기 쉬 운 방식 을 제공 합 니 다.
import create_binary_tree # ， py
def get_layers(root, switch=True):
"""
:param pRoot:
:param switch: “ ” ， ， “ ” ，
:return: ， ，
"""
if not root: #
return [] #
cur_layer = [root] #
result = [] #
right2left = False # ，
while cur_layer: #
cur_val = [] #
next_layer = [] #
for node in cur_layer: #
cur_val.append(node.val) #
if node.left: #
next_layer.append(node.left) #
if node.right: #
next_layer.append(node.right) #
if right2left: #
cur_val.reverse() #
if cur_val: #
result.append(cur_val) #
cur_layer = next_layer #
if switch: # “ ”
right2left = not right2left #
return result #
if __name__ == "__main__":
#
s = Solution()
r = create_binary_tree([1,2,3,4,5,6,7])
print(get_layers(r))
# ：[[1], [3, 2], [4, 5, 6, 7]]
여기 서 변수 (right2left) 의 불 값 을 계속 뒤 집어 인접 층 의 인쇄 순서 가 다 르 고 함수 에 스위치 (switch) 를 설정 하여 '의' 자형 인쇄 가 필요 한 지 여 부 를 결정 합 니 다. 독자 들 은 이 스위치 를 닫 으 려 고 시도 할 수 있 습 니 다. 그러면 실험 결 과 는 차원 이 옮 겨 다 니 는 것 과 다 름 없습니다.
4. 이 진 트 리 의 직렬 화 와 역 직렬 화
모든 노드 가 정수 인 이 진 트 리 에 대해 우 리 는 하나의 문자열 로 이 나 무 를 대표 할 수 있 습 니 다. 이 과정 은 이 진 트 리 의 직렬 화 라 고 합 니 다. 한 나 무 를 대표 하 는 문자열 서열 에 따라 이 나 무 를 재 구성 하 는 과정 은 이 진 트 리 의 반 직렬 화 입 니 다.직렬 화 와 반 직렬 화 는 서로 역 과정 이 고 이 진 트 리 의 역 주 행 과 이 진 트 리 의 구축 은 서로 역 과정 이다.여 기 는 두 개의 일 치 를 유지 해 야 합 니 다.
옮 겨 다 니 는 순서 가 일치 합 니 다. 이 진 트 리 를 직렬 화 할 때 앞 순 서 를 옮 겨 다 니 는 방식 을 사용 하면 이 진 트 리 를 재 구성 하려 면 앞 순 서 를 따라 재 구성 해 야 합 니 다.
주요 문자 대응: 이 진 트 리 의 시공 간 노드 를 '\ #' 로 정렬 하면 이 진 트 리 를 재 구성 할 때 '\ #' 을 만 났 을 때 빈 노드 를 구성 해 야 합 니 다.
1. 이 진 트 리 의 서열 화
이 진 트 리 의 직렬 화 과정 은 재 귀 를 사용 하 는 것 이 매우 간단 합 니 다. 우 리 는 재 귀 전 순서 로 옮 겨 다 니 는 방식 으로 실현 할 수 있 습 니 다.
def serialize(root):
"""
:param root:
:return:
"""
if not root:
return "#"
return str(root.val) + ',' + serialize(root.left) + ',' + serialize(root.right)
2. 이 진 트 리 의 역 직렬 화
상기 직렬 화 과정 과 유사 하 게 우 리 는 앞 순 서 를 옮 겨 다 니 는 방식 으로 이 진 트 리 를 재건 한다.
def deserialize(s):
"""
:param s:
:return:
"""
def helper(nodes):
if not nodes:
return None
val = nodes.pop(0) #
if val == '#': # “#”
node = None #
else: #
node = TreeNode(int(val)) #
node.left = helper(nodes) #
node.right = helper(nodes) #
return node #
nodes = s.split(',') #
return helper(nodes) #
5. 이 진 트 리 의 속성
1. 이 진 트 리 의 최대 깊이
뿌리 결점 에서 잎 결점 까지 순서대로 지나 가 는 결점 (뿌리, 잎 결점 포함) 은 나무의 한 경 로 를 형성 하고 가장 긴 경로 의 길 이 는 나무의 깊이 이다.이 진 트 리 의 최대 깊이 를 찾 습 니 다.
이 문 제 는 파워 버튼 에 대응 하 는 문 제 는 [문제 104. 이 진 트 리 의 최대 깊이] 입 니 다. 여기 서 우 리 는 재 귀 법 과 교체 법 두 가지 방식 으로 이 문 제 를 해결 합 니 다.재 귀 법 은 실제 적 으로 모든 결점 이 있 는 차원 의 최대 치 를 얻 는 것 이다.
def max_depth(root):
"""
:param root:
:return:
"""
if not root: #
return 0 #
max_left = max_depth(root.left) #
max_right = max_depth(root.right) #
return max(max_left, max_right) + 1 # ，
교체 법 은 층 차 를 옮 겨 다 니 는 것 과 유사 하 다. 다만 여 기 는 각 층 의 결점 을 기록 할 필요 가 없고 통계 가 달성 하 는 차원 만 필요 하 다.
def get_depth(root):
"""
:param root:
:return:
"""
if not root: #
return 0 #
cur_layer = [root] #
depth = 0 #
while cur_layer: # ，
next_layer = [] #
for node in cur_layer: #
if node.left: #
next_layer.append(node.left) #
if node.right: #
next_layer.append(node.right) #
cur_layer = next_layer #
depth += 1 # +1
return depth #
테스트 용례:
if __name__ == "__main__":
r = create_binary_tree([1, 2, 3, 4, 5, 6, 7])
print(max_depth(r))
# ：3
2. 이 진 트 리 의 최소 깊이
최소 깊이 는 뿌리 노드 에서 최근 잎 노드 까지 의 가장 짧 은 경로 의 노드 수량 이다.이 문 제 는 [111. 이 진 트 리 의 최소 깊이] 에서 유래 한 것 으로 해법 은 위의 문제 와 유사 하 다. 여기 서 우 리 는 재 귀적 으로 실현 하고 더욱 편리 하 다.
def min_depth(root):
"""
:param root:
:return:
"""
if not root: #
return 0 #
left_min_depth = min_depth(root.left) #
right_min_depth = min_depth(root.right) #
if left_min_depth > 0 and right_min_depth > 0: # 0
res = min(left_min_depth, right_min_depth) + 1 # +1
else: #
res = max(left_min_depth, right_min_depth) + 1 # ， +1
return res
테스트 용례:
if __name__ == "__main__":
r = create_binary_tree([1, 2, 3, 4, 5, 6, 7])
print(min_depth(r))
# ：3
3. 모든 경로
이 문제 의 출처 [257. 이 진 트 리 의 모든 경로] 는 구체 적 인 해법 을 볼 수 있 습 니 다.
def get_paths(root):
"""
root
:type root:
:rtype: ，
"""
def helper(root, path, res):
"""
:param root:
:param path: root
:param res:
:return:
"""
cur_path = path + [root.val] #
if not root.left and not root.right: #
res.append(cur_path) #
return #
if root.left: #
helper(root.left, cur_path, res) #
if root.right: #
helper(root.right, cur_path, res) #
if not root: #
return [] # ，
paths = [] #
helper(root, [], paths) #
return paths #
테스트 용례:
if __name__ == "__main__":
r = create_binary_tree([1, 2, 3, 4, 5, 6, 7])
print(min_depth(r))
# ：[[1, 2, 4], [1, 2, 5], [1, 3, 6], [1, 3, 7]]
4. 대칭 이 진 트 리
이 문 제 는 [101. 대칭 이 진 트 리] 에서 유래 하여 함수 로 이 진 트 리 가 미 러 이 진 트 리 인지 아 닌 지 를 판단 합 니 다.좌우 자목 거울 이 대칭 적 이면 이 진 트 리 도 대칭 적 이다.
def isSymmetric(root):
"""
:param root:
:return:
"""
def is_mirror(p, q): #
if not p and not q: #
return True #
elif not p and q or p and not q: #
return False #
else: #
# ： ， ，
return p.val == q.val and is_mirror(p.left, q.right) and is_mirror(p.right, q.left)
return is_mirror(root, root) #
테스트 용례:
if __name__ == '__main__':
r = create_binary_tree([1, 2, 3, 4, 5, 6, 7])
print(is_symmetric(r))
# ：False
5. 이 진 트 리 조작
1. 이 진 트 리 의 거울
두 갈래 나 무 를 거울 두 갈래 나무 로 바꾸다.뿌리 노드 의 좌우 자 나 무 를 교환 한 후 좌우 자 나 무 를 거울 나무 로 바 꾸 면 된다.
def mirror(root):
"""
:param root:
:return:
"""
if root:
root.left, root.right = root.right, root.left #
mirror(root.left) #
mirror(root.right)
테스트 용례:
if __name__ == '__main__':
r = create_binary_tree([1, 2, 3, 4, 5, 6, 7])
print(get_layers(r, False)) # “ ”
mirror(r)
print(get_layers(r, False))
# ：[[1], [2, 3], [4, 5, 6, 7]]， [[1], [3, 2], [7, 6, 5, 4]]
6. 통합
우 리 는 상기 코드 를 통합 하여 실례 화 된 이 진 트 리 를 구축 합 니 다.
class BinaryTree:
def __init__(self, node_vals):
self.tree = create_binary_tree(node_vals)
@staticmethod #
def create_binary_tree(nodes):
def helper(node, i):
if i < len(nodes):
if nodes[i] in ['#', None]:
return None
else:
node = TreeNode(nodes[i])
node.left = helper(node.left, 2 * i + 1)
node.right = helper(node.right, 2 * i + 2)
return node
return node
root = TreeNode(0)
root = helper(root, 0)
return root
#
@property
def serialize(self):
s = lambda r: str(r.val) + ',' + s(r.left) + ',' + s(r.right) if r else "#"
return s(self.tree)
# ，
@property
def pre_order(self):
helper = lambda n: [n.val] + helper(n.left) + helper(n.right) if n else []
return helper(self.tree)
# ，
@property
def in_order(self):
helper = lambda n: helper(n.left) + [n.val] + helper(n.right) if n else []
return helper(self.tree)
# ，
@property
def post_order(self):
helper = lambda n: helper(n.left) + helper(n.right) + [n.val] if n else []
return helper(self.tree)
# ，
@property
def level_order(self):
def helper(node, level):
if not node:
return
else:
res[level - 1].append(node.val)
if len(res) == level:
res.append([])
helper(node.left, level + 1)
helper(node.right, level + 1)
res = [[]]
helper(self.tree, 1)
return res[:-1]
#
@property
def max_depth(self):
helper = lambda r: max(helper(r.left), helper(r.right))+1 if r else 0
return helper(self.tree)
#
@property
def min_depth(self):
def helper(root):
if not root:
return 0
left_min_depth = helper(root.left)
right_min_depth = helper(root.right)
if left_min_depth > 0 and right_min_depth > 0:
res = min(left_min_depth, right_min_depth) + 1
else:
res = max(left_min_depth, right_min_depth) + 1
return res
return helper(self.tree)
#
@property
def all_paths(self):
def helper(root, path, res):
cur_path = path + [root.val]
if not root.left and not root.right:
res.append(cur_path)
return
if root.left:
helper(root.left, cur_path, res)
if root.right:
helper(root.right, cur_path, res)
if not self.tree:
return []
paths = []
helper(self.tree, [], paths)
return paths
#
@property
def is_symmetric(self):
def helper(p, q):
if not p and not q:
return True
elif not p and q or p and not q:
return False
else:
return p.val == q.val and helper(p.left, q.right) and helper(p.right, q.left)
return helper(self.tree, self.tree)
#
def flip(self):
def helper(root):
if root:
root.left, root.right = root.right, root.left
helper(root.left)
helper(root.right)
helper(self.tree)
장식 부호 @ property 는 클래스 속성 을 표시 합 니 다. 테스트 용례 는:
if __name__ == '__main__':
nodes = [1, 2, 3, 4, 5, 6, 7, 8]
print(' ， ：{}.'.format(nodes))
bt = BinaryTree(nodes)
print(' ：{}'.format(bt.serialize))
print(' ：{}'.format(bt.pre_order))
print(' ：{}'.format(bt.in_order))
print(' ：{}'.format(bt.post_order))
print(' ：{}'.format(bt.level_order))
print(' ：{}'.format(bt.max_depth))
print(' ：{}'.format(bt.min_depth))
print(' ：{}'.format(bt.all_paths))
print(' ：{}'.format(bt.is_symmetric))
print(' ')
bt.flip()
print(' ：{}'.format(bt.level_order))
이 이 진 트 리 [1, 2, 3, 4, 5, 6, 7, 8] 는 실제로:
1
/ \
2 3
/ \ / \
4 5 6 7
/
8
테스트 결 과 는:
：1,2,4,8,#,#,#,5,#,#,3,6,#,#,7,#,#
：[1, 2, 4, 8, 5, 3, 6, 7]
：[8, 4, 2, 5, 1, 6, 3, 7]
：[8, 4, 5, 2, 6, 7, 3, 1]
：[[1], [2, 3], [4, 5, 6, 7], [8]]
：4
：3
：[[1, 2, 4, 8], [1, 2, 5], [1, 3, 6], [1, 3, 7]]
：False
：[[1], [3, 2], [7, 6, 5, 4], [8]]
질문 이나 조언 이 있 으 시 면 댓 글 남 겨 주세요 ~
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
