면접 문제 32.2: 두 갈래 나무를 여러 줄로 인쇄

제목 설명

위에서 아래로 층별로 두 갈래 트리를 인쇄하고 같은 층의 결점은 왼쪽에서 오른쪽으로 출력합니다.층마다 줄을 출력합니다.
지식
두 갈래 나무, 대열

Qiang의 사고방식

이 문제는 면접 문제 32.1에 비해 지점 수출 요구가 많았다.지난 문제를 토대로 이것도 간단하게 실현되었다.만약에 우리가 루트 노드 뒤에 줄이 끝나는 표지 위치를 추가한다면, 이 줄이 모두 훑어본 후에, 우리는 이 표지 위치를 대기열의 맨 끝에 놓아야 한다. 그러면 두 번째 줄의 맨 뒤에 표지 위치를 하나 더 추가하는 것과 같아서, 언제 줄을 바꾸어야 할지 구분할 수 있기 때문이다.

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    #  [[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if pRoot==None:
            return []
        result=[]
        l=['#', pRoot]
        while l!=['#']:
            c=l.pop(0)
            if c=='#':
                result.append([])
                l.append('#')
                continue
            result[-1].append(c.val)
            if c.left!=None:
                l.append(c.left)
            if c.right!=None:
                l.append(c.right)
        return result

나는 언제 수조에 새 줄을 추가할지 판단해야 하기 때문에, 표지 위치를 줄 뒤에 두지 않고 줄 앞에 두었다.이것은 결코 문제를 푸는 사고방식에 영향을 주지 않는다.
주의해야 할 것은 표지 위치가 대기열에 계속 존재하기 때문에 최종 반복 종료 조건은 대기열에 표지 위치만 있을 때이다.

책 속의 사고방식

책에서 이 문제에 대한 처리도 이전 문제를 토대로 두 개의 변수를 추가하여 해결했다. 하나는 현재 줄의 남은 노드 수를 저장하고 다른 하나는 다음 줄의 노드 수를 저장한다.이렇게 하면 얼마나 많은 노드를 출력해야 줄을 바꿀 수 있는지 알 수 있으며, 동시에 줄을 바꿀 때 다음 줄의 노드 수의 계수를 시작할 것이다.

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    #  [[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if pRoot == None:
            return []
        res=[[]]
        l=[pRoot]
        c_number=1
        n_number=0
        while len(l)!=0:
            n=l.pop(0)
            res[-1].append(n.val)
            c_number-=1
            if n.left!=None:
                l.append(n.left)
                n_number+=1
            if n.right!=None:
                l.append(n.right)
                n_number+=1
            if c_number==0 and n_number!=0:
                c_number=n_number
                n_number=0
                res.append([])
        return res

작가 오리지널, 전재 및 기타 질문은 메일박스로 연락하세요: [email protected]. 개인 웹 사이트:https://www.myqiang.top.