[소백 검지 offer] 네 번째 문제 두 갈래 나무 재건.

7044 단어 Algorithm

4 두 갈래 나무 재건


두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하십시오. 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {1,2,4,7,3,5,6,8}와 중간 순서 반복 시퀀스 {4,7,2,1,5,3,8,6}를 입력하면 두 갈래 트리를 재건하고 되돌려줍니다.
  • 앞의 순서는 뿌리 결점을 먼저 방문하고 왼쪽 결점을 방문하며 마지막으로 오른쪽 결점을 방문한다.두 갈래 나무의 앞 순서가 두루 다니는 순서는 10, 6, 4, 8, 14, 12, 16이다
  • 중순으로 왼쪽 결점을 방문하고 뿌리 결점을 방문하며 마지막으로 오른쪽 결점을 방문한다.두 갈래 나무의 중서가 두루 다니는 순서는 4, 6, 8, 10, 12, 14, 16이다
  • 뒤에 차례대로 왼쪽 결점을 방문하고 오른쪽 결점을 방문하며 마지막으로 뿌리 결점을 방문한다.두 갈래 나무의 뒷차례가 두루 다니는 순서는 4, 8, 6, 12, 16, 14, 10이다
  • 너비는 먼저 트리의 1층 결점에 접근한 다음에 트리의 2층 결점에 접근한다...맨 아래 결점까지 접근한다.같은 층 결점에서 왼쪽에서 오른쪽으로 순서대로 접근합니다.두 갈래 나무의 너비를 우선적으로 훑어보는 순서는 10, 6, 14, 4, 8, 12, 16이다

  • 더미는 가장 큰 무더기와 가장 작은 무더기로 나뉜다
  • 가장 큰 무더기 중 뿌리 결점의 값이 가장 크다
  • 최소 더미 중 뿌리 결점의 값이 가장 작다

  • 붉은색 검은 나무는 나무의 결점을 붉은색, 검은색 두 가지 색으로 정의하고 규칙을 통해 뿌리 결점에서 잎 결점까지의 최장 경로의 길이가 최단 경로의 두 배를 넘지 않도록 확보한다.
    class TreeNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
    
    class Solution:
        def reConstructBinaryTree(self, pre, tin):
            # write code here
            print(pre)
            print(tin)
            
            if pre:
                l=len(pre)
                if l==1:
                    tree=TreeNode(pre[0])
                    return tree
                
                t = tin.index(pre[0])
                tree = TreeNode(pre[0])
                tree.left=self.reConstructBinaryTree(pre[1:t+1],tin[0:t])
                tree.right=self.reConstructBinaryTree(pre[t+1:l],tin[t+1:l])
                return tree
    
    pre=[1,2,4,7,3,5,6,8]
    tin=[4,7,2,1,5,3,8,6]
    task =Solution()
    t=task.reConstructBinaryTree(pre,tin)
    
    '''   
    TreeNode  
     , self.
    '''
    

    좋은 웹페이지 즐겨찾기