두 갈래 나무 재건

나무에 관해서는 면접 때 두 갈래 나무를 많이 고찰한다
폭 우선 및 깊이 우선

# python3
from queue import Queue
class Solution:
    #  （ ）
    def layertraverse(self, root):
        # 1, 2, 3, 4, 5, 6, 7, 8
        que = Queue()
        que.put(root)
        while not que.empty():
            node = que.get()
            print(node.value)
            if node.left:
                que.put(node.left)
            if node.right:
                que.put(node.right)

그 중 깊이를 우선적으로 훑어보기:

앞의 순서를 두루 훑어보다

class Solution:
    #  
    def recuristive(self, root):
        if root is not None:
            print(root.value)
            self.recuristive(root.left)
            self.recuristive(root.right)
    #  
    def iterator(self, root):
        stack = [root]
        while len(stack) > 0:
            node = stack.pop()
            print(node.value)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)

중서가 두루 다니다

class Solution:
    #  
    def recuristive(self, root):
        if not root:
            self.recuristive(root.left)
            print(root.value)
            self.recuristive(root.right)
    #  
    def iterator(self, root):
        # 4 7 2 1 5 3 8 6
        stack = []
        node = root
        while len(stack) > 0 or node:
            if node:
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()
                print(node.value)
                node = node.right

뒷차례가 두루 다니다

class Solution:
    #  
    def recuristive(self, root):
        if root:
            self.recuristive(root.left)
            self.recuristive(root.right)
            print(root.value)
            
    #  
    def iterator(self, root):
        # 7 4 2 5 8 6 3 1
        stack_pre_right = [root]
        stack = []
        while len(stack_pre_right) > 0:
            node = stack_pre_right.pop()
            stack.append(node)
            if node.left:
                stack_pre_right.append(node.left)
            if node.right:
                stack_pre_right.append(node.right)
        while stack:
            node = stack.pop()
            print(node.value)

이 몇 가지 반복 알고리즘은 귀속 실현과 순환 실현으로 나뉘는데, 여섯 가지 방법은 숙련되어야 한다
다른 두 갈래 나무의 특례:

두 갈래 검색 트리 - 왼쪽 노드는 항상 루트 노드보다 작고 오른쪽 노드는 루트 노드보다 크다. 우리는 평균적으로 O(logn)의 시간 내에 수치에 따라 두 갈래 검색 트리에서 노드를 찾을 수 있다

더미-더미는 최소 더미와 최대 더미로 나뉘는데 각각 대응하는 규칙은 뿌리 노드가 가장 작고 뿌리 노드가 가장 커서 가장 빠른 값을 얻을 수 있다

붉은색 검은 나무 - 붉은색 검은 나무는 나무의 노드를 붉은색, 검은색 두 가지 색깔로 정의하고 규칙을 통해 뿌리 노드에서 잎 노드까지의 최장 경로의 길이가 최단 경로의 두 배를 넘지 않도록 확보한다.C++의 STL에서 set,multiset,map,multimap 등 데이터 구조는 모두 붉은 검은 나무를 바탕으로 이루어진다

제목: 두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하십시오. 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {1, 2, 4, 7, 3, 5, 6, 8}와 중간 순서 반복 시퀀스 {4, 7, 2, 1, 5, 3, 8, 6}를 입력하면 두 갈래 나무를 재건합니다.

class Solution:
    #  
    def func(self, mid_seq, pre_seq):
        mid_dict = {value: index for index, value in enumerate(mid_seq)}
        return self.create_tree(mid_dict, mid_seq, 0, len(mid_seq)-1, pre_seq, 0, len(pre_seq)-1)
    
    def create_tree(self, mid_dict, mid_seq, mid_beg, mid_end, pre_seq, pre_beg, pre_end):
        if mid_beg > mid_end or pre_beg > pre_end:
            return None
        root = TreeNode()
        root.value = pre_seq[pre_beg]
        
        mid = mid_dict[pre_seq[pre_beg]]
        num = mid - mid_beg
        
        root.left = self.create_tree(mid_dict, mid_seq, mid_beg, mid-1, pre_seq, pre_beg+1, pre_beg+num)
        root.right = self.create_tree(mid_dict, mid_seq, mid+1, mid_end, pre_seq, pre_beg+num+1, pre_end)
        return root

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

두 갈래 나무 재건 - jzoffer

좋은 웹페이지 즐겨찾기