[자료구조] 이진트리 주요 알고리즘

응용 문제를 잘 풀기 위해 기본을 탄탄하게 만들어야 한다.

이진트리 문제 중 기본에 해당하는 문제들을 익히면서 나만의 접근법을 완성시키자!

 

1. 이진트리 최대 깊이 탐색(dfs 사용하였다.)

leetcode.com/problems/maximum-depth-of-binary-tree

# 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:
    max_dep =0
    def maxDepth(self, root: TreeNode) -> int:
        def dfs(node, depth):
            if not node :
                self.max_dep = max(self.max_dep,depth)
                return
            
            dfs(node.left, depth+1)
            dfs(node.right, depth+1)
            
        dfs(root,0)
        return self.max_dep

 

2. 이진트리 반전

leetcode.com/problems/invert-binary-tree

 

각각 dfs, bfs 풀이다.

# 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 invertTree(self, root: TreeNode) -> TreeNode:
        
        def dfs(node):
            if not node:
                return
            
            node.left, node.right = dfs(node.right), dfs(node.left)
            return node
        
        dfs(root)
        return root

# 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 invertTree(self, root: TreeNode) -> TreeNode:
        queue = collections.deque([root])
        
        while queue:
            node = queue.popleft()
            if node:
                node.left, node.right = node.right, node.left
                
                queue.append(node.left)
                queue.append(node.right)
                
        return root

 

3. 두 이진트리 병합

leetcode.com/problems/merge-two-binary-trees

# 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 mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        if root1 and root2:  
            node = TreeNode(root1.val+root2.val)
            node.left = self.mergeTrees(root1.left,root2.left)
            node.right = self.mergeTrees(root1.right,root2.right)
            return node
        else:
            return root1 or root2

# 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 mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        
        def dfs(node1,node2):
            if node1 and node2:
                node1.val += node2.val
                node1.left = dfs(node1.left, node2.left)
                node1.right = dfs(node1.right, node2.right)
                
            elif node2 and not node1:
                node1 = node2
                
            return node1
         
        return dfs(root1,root2)