Python-BinaryTree

앞뒤 세 가지 역행 방법은 좌우 결점의 역행 순서가 모두 같다(앞뒤 왼쪽, 뒤쪽 오른쪽). 유일하게 다른 것은 뿌리 노드의 출현 위치이다.

 

중역:

먼저 왼쪽에 뿌리를 내리고 나중에 오른쪽에 뿌리를 내리다

반복 구현:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def MidTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ans = []
        
        def recurse(root):
            if root:
                recurse(root.left)
                ans.append(root.val)
                recurse(root.right)
        
        recurse(root)
        
        return ans

순환 실현:

트리의 순환 작업은 기본적으로 창고 (stack) 구조에 사용됩니다.현재 결점 (curr) 의 왼쪽 결점push를 창고로 옮겨 현재 결점 (curr) 이 None이 될 때까지 반복합니다.이때 팝업 창고의 첫 번째 요소는 현재 결점으로 설정하고 이 결점의value 값을 출력하며 이 결점의 오른쪽 트리를 훑어보기 시작합니다.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def MidTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = []
        ans = []
        curr = root
        
        while stack or curr:
            if curr:
                stack.append(curr)
                curr = curr.left
            else:
                curr = stack.pop()
                ans.append(curr.val)
                curr = curr.right
        return ans

순서대로 훑어보기:

먼저 뿌리를 내리고 왼쪽에서 오른쪽으로

반복 구현:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
     
        ans = []
        
        def recurse(root):
            
            if root != None:
                ans.append(root.val)
                recurse(root.left)
                recurse(root.right)
        
        recurse(root)
        
        return ans
        

순환 실현:

먼저 보고 먼저 두루 훑어보다.우리는 여전히 창고 stack을 사용합니다. 앞의 순서가 루트 좌우이기 때문에 매번 현재 결점curr를 출력하고 현재 결점push를 창고에 넣은 다음 왼쪽 결점을 현재 결점으로 설정합니다. 현재 결점 (curr) 이 None일 때까지.팝업 창고 꼭대기의 첫 번째 요소는 현재 결점으로 설정하고 이 결점의 오른쪽 나무를 훑어보기 시작합니다.입고와 출고 조건, 순환 종료 조건은 중차와 똑같다.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        
        stack = []
        ans = []
        curr = root
        
        while stack or curr:
            if curr:
                ans.append(curr.val)
                stack.append(curr)
                curr = curr.left
            else:
                curr = stack.pop()
                curr = curr.right
                
        return ans

다음 순서를 반복합니다.

먼저 왼쪽에서 다시 오른쪽 뒤쪽

반복 구현:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ans = []
        
        def recurse(root):
            if root:
                recurse(root.left)
                recurse(root.right)
                ans.append(root.val)
        
        recurse(root)
        return ans

순환 실현:

뒤의 순서가 좌우 중간이기 때문에 우리는 그것을 거꾸로 하면 뒤의 순서가 중우 왼쪽으로 바뀌고 다시 역순으로 변한다.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = []
        ans = []
        curr = root
        while stack or curr:
            if curr:
                ans.append(curr.val)
                stack.append(curr)
                curr = curr.right
            else:
                curr = stack.pop()
                curr = curr.left
        return ans[::-1]
       

계층 이동:

층차적 훑어보기도 폭 우선 훑어보기라고 할 수 있다. 먼저 나무의 1층 결점을 방문하고, 다시 나무의 2층 결점을 방문한다...그리고 맨 아래 결점까지 계속 방문합니다.같은 층 결점에서 왼쪽에서 오른쪽으로 순서대로 접근합니다.

두 갈래 나무의 층별 출력은 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 나무의 노드를 인쇄한다.층마다 줄을 출력합니다.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        ans = []
        queue = [root]
        
        if not root:
            return []
        
        while queue:
            temp = []
            i = 0
            numQueue = len(queue) # 
            
            while i < numQueue:   # 
                curr = queue.pop(0)
                temp.append(curr.val)
                
                if curr.left:
                    queue.append(curr.left)
                if curr.right:
                    queue.append(curr.right)
                    
                i += 1
            ans.append(temp)
        return ans