[LeetCode] 이진트리 문제 -Feat: 재귀

이진트리

이진트리란?

컴퓨터 과학에서, 이진 트리(二進-, 영어: binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다.

이진트리 관련 문제

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

• 이진트리를 병합하는 방법

풀이법_#1. 재귀함수 사용

파이썬 클래스 매서드를 재귀호출하려면 함수이름앞에 self. 을 붙여야함.

# 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: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if (not root1):
            return root2
        elif (not root2):
            return root1

        node = TreeNode(root1.val + root2.val)
        node.left = self.mergeTrees(root1.left, root2.left)
        node.right = self.mergeTrees(root1.right, root2.right)

        return node

116번

풀이_#1

재귀함수 사용
재귀함수를 사용할때는 재귀함수의 1번의 싸이클이 무엇을 의도하는지 생각한 뒤 짜야한다.
아래 코드의 경우에는 재귀함수 1번의 싸이클이 인자로 받은 root라는 이름의 노드의 left 와 right child 의 next 를 지정해 주는 역할을 하며,
당연히 재귀가 끝나는 조건은 root 라는 이름이 left 나 right child 를 가지지 않을때이다.
문제의 Follow-up 요구사항에 나와있듯이, space Time O(1) 로 구현했.

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution(object):
    def connect(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        if (not root):
            return root

        if root.left:
            root.left.next = root.right

        if root.right and root.next:
            root.right.next = root.next.left

        if root.left:
            self.connect(root.left)
        if root.right:
            self.connect(root.right)

        return root