《 검 지 offer 》 Day 2

《 검 지 offer 》 Day 2
끝 에서 끝까지 링크 를 인쇄 하 다.
제목: 링크 의 끝 점 을 입력 하고 끝 에서 끝까지 모든 노드 의 값 을 출력 합 니 다.
기 존의 링크 의 데이터 구 조 를 바 꾸 지 않 을 때 링크 를 처음부터 인쇄 하면 링크 의 모든 요 소 를 기록 하고 옮 겨 다 닌 후에 인쇄 할 수 밖 에 없다.이 과정 은 스 택 의 작업 에 부합 합 니 다. 즉, 먼저 들 어간 후에 나 옵 니 다. 우 리 는 먼저 요 소 를 추가 한 다음 에 가장 먼저 추 가 된 마지막 출력 입 니 다.

def print_list_reversingly_iteratively(head):
    #           
    node_list = []
    
    if not head:
        return None
    
    cur = head
    while cur:
        #   
        node_list.append(cur.elem)
        cur = cur.next

    while node_list:
        #   
        print(node_list.pop(), end=' ')
    print()

그리고 재 귀 작업 을 통 해 재 귀 는 본질 적 으로 스 택 의 구조 이다. 먼저 앞으로 찾 아 재 귀 수출 조건 을 만족 시 킨 다음 에 역방향 으로 전달 하기 때문에 재 귀 로 역방향 링크 의 수출 도 할 수 있다.

def print_list_reversingly_recursively(head):
    
    if head != None:
        if head.next != None:
            print_list_reversingly_recursively(head.next)
        print(head.elem, end=' ')

이 진 트 리 재건
제목: 한 이 진 트 리 의 앞 순 서 를 입력 하고 중간 순 서 를 옮 겨 다 니 는 결 과 를 입력 하 십시오. 이 이 진 트 리 를 다시 만 드 십시오.입력 한 앞 순 서 를 옮 겨 다 니 거나 중간 순 서 를 옮 겨 다 니 는 결 과 는 중복 되 는 숫자 가 없다 고 가정 합 니 다.예 를 들 어, 입력 전 시퀀스 {1, 2, 4, 7, 3, 5, 6, 8} 과 중 시퀀스 {4, 7, 2, 1, 5, 3, 8, 6} 을 입력 하면 이 진 트 리 를 재 구축 하고 머리 노드 를 출력 합 니 다.
이 진 트 리 의 앞 순 서 는 뿌리 노드 의 위 치 를 알 수 있 고 뿌리 노드 의 값 에 따라 중간 순서 로 옮 겨 다 니 는 위 치 를 찾 을 수 있 으 며 더 나 아가 좌우 서브 트 리 로 나 눌 수 있다.그 다음 에 모든 좌우 서브 트 리 는 같은 방법 에 따라 대응 하 는 왼쪽 노드 와 오른쪽 노드 를 찾 을 수 있 기 때문에 재 귀 를 통 해 전체 이 진 트 리 를 구축 할 수 있다.

#      
class binaryTreeNode():
    def __init__(self, elem=None):
        self.elem = elem
        self.left = None
        self.right = None

#      
def construct_tree(preorder, inorder):
    
    if (not preorder) and (not inorder):
        return None
    
    root_value = preorder[0]
    root = binaryTreeNode(root_value)
    #            
    cut = inorder.index(root_value)
    root.left = construct_tree(preorder[1:1+cut], inorder[:cut])
    root.right = construct_tree(preorder[cut+1:], inorder[cut+1:])
    
    return root
#   
preorder = [1,2,4,7,3,5,6,8]
inorder = [4,7,2,1,5,3,8,6]
tree = construct_tree(preorder, inorder)

#     ，          
def travel_tree(tree):
    if not tree:
        return None
    
    equeue = [tree]
    while equeue:
        
        if equeue[0].left is not None:
            equeue.append(equeue[0].left)
        if equeue[0].right is not None:
            equeue.append(equeue[0].right)
        print(equeue.pop(0).elem)

피 보 나치 수열
제목 1: 피 보 나치 수열 n 번
함 수 를 써 서 n 을 입력 하고 피 보 나치 수열 의 n 항 을 구하 세 요.피 보 나치 수열 의 정 의 는 다음 과 같다. KaTeX parse error: Unknown column alignment: * at position 45:... {\ begin {array} {*̲{20}{c}} {\begi…
귀속 해법:

def Fibonacci_recursively(n):
    if n <= 0:
        return 0
    
    if n == 1:
        return 1
    
    return Fibonacci_recursively(n-1) + Fibonacci_recursively(n-2)

동적 계획 해법:
위의 정 의 는 하나의 동적 계획 의 상태 방정식 으로 삼 아 교체 하면 n 항 을 내 놓 을 수 있다.

def Fibonacci_dynamic(n):
    res = [0, 1]
    
    if n == 0:
        return res[0]
    if n == 1:
        return res[1]
    
    for i in range(2, n+1):
        tmp = res[0] + res[1]
        res[0] = res[1]
        res[1] = tmp
    
    return res[1]