[알고리즘] Level Order, N-array Tree Postorder, Preorder

포인트

• 오늘은 비슷한 문제를 전부 풀어보려고 합니다. 레벨 오더는 트리에서 층마다 순회를 하는 방법으로 Preorder, Inorder, Postorder 하고는 또 다른, Tree를 순회하는 방법입니다. 
• 또한, 여기 있는 문제들은 트리 여러 종류들을 순회하는 방법들이니 참고하시면 좋을 것 같습니다. 

https://leetcode.com/problems/n-ary-tree-postorder-traversal/

N-ary Tree Postorder Traversal - LeetCode

 

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def __init__(self):
        self.result = []
        
    def order(self, node:'Node')-> None:
        if node is not None:
            self.result.append(node.val)
            for x in node.children:
                self.order(x)
            
    def preorder(self, root: 'Node') -> List[int]:
        self.order(root)
        return self.result

https://leetcode.com/problems/n-ary-tree-preorder-traversal/

N-ary Tree Preorder Traversal - LeetCode

 

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""


class Solution:
    def __init__(self):
        self.result = []
        
    def order(self, node:'Node')-> None:
        if node is not None:
            for x in node.children:
                self.order(x)
            self.result.append(node.val)

    def postorder(self, root: 'Node') -> List[int]:
        self.order(root)
        return self.result

https://leetcode.com/problems/binary-tree-level-order-traversal/

Binary Tree Level Order Traversal - LeetCode

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        result = []
        if root is None:
            return []
        else:
            q = deque([root])
            result = []
            while q:
                line = []
                for _ in range(len(q)):
                    x = q.popleft()                    
                    line.append(x.val)
                    for nx in (x.left, x.right):
                        if nx is not None:
                            q.append(nx)
                else:
                    result.append(line)
            else:
                return result

https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

Binary Tree Level Order Traversal II - LeetCode

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []
        else:
            q = deque([root])
            result =[]
            while q:
                line = []
                for _ in range(len(q)):
                    x = q.popleft()
                    line.append(x.val)
                    for nx in (x.left, x.right):
                        if nx is not None:
                            q.append(nx)
                else:
                    result.append(line)
            else:
                return result[::-1]

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

Binary Tree Zigzag Level Order Traversal - LeetCode

python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []
        else:
            q = deque([root])
            result =[]
            flag = True
            while q:
                line = []
                for _ in range(len(q)):
                    x = q.popleft()
                    line.append(x.val)
                    for nx in (x.left, x.right):
                        if nx is not None:
                            q.append(nx)
                else:
                    result.append(line) if flag else result.append(line[::-1])
                    flag = False if flag else True
            else:
                return result

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다.