[DFS/BFS]99클럽 코테 스터디 17일차 TIL + 0094-binary-tree-inorder-traversal

94. Binary Tree Inorder Traversal

Easy

---

Given the root of a binary tree, return the inorder traversal of its nodes' values.

 

Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

 

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

 

Follow up: Recursive solution is trivial, could you do it iteratively?

 

<내코드> : 35분 20초

# 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

# ⊙ 전위 순회(preorder traverse) : 뿌리(root)를 먼저 방문
# ⊙ 중위 순회(inorder traverse) : 왼쪽 하위 트리를 방문 후 뿌리(root)를 방문
# ⊙ 후위 순회(postorder traverse) : 하위 트리 모두 방문 후 뿌리(root)를 방문

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        output = []
        def inorder(root, list):
            if root:
                inorder(root.left,list)
                output.append(root.val)
                inorder(root.right,list)
            return output

        # if not root:
        #     return None
        
        return inorder(root,output)

1. 헷갈린 부분

문제가 여러단계 있었다

- 우선 중위 순회인경우 방향에 대해서 헷갈린것이 있었다.

이전에 풀었던것을 바탕으로 하였음

 

- print가 아님

=> 이 경우 list에 다가 append 하는 방식으로 해야함

 

- list 가 케이스마다 초기화되지않음

=> 메인 실행문제 메소드에 list를 한번 선언하고, 실질적으로 재귀하는것은 별도 메소드를 만들어서 순회시킴

 

<모범사례>

 - 반복문을 사용한경우

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        stack, output = [], []
        current = root

        while current or stack:
            while current:
                stack.append(current)
                current = current.left
            current = stack.pop()
            output.append(current.val)
            current = current.right

        return output

 

문제의 조건에서 반복문으로 풀것을 요구하고있음 -> 재귀호출의 한계, 스택 오버플로우 피하기 위함

 

<보충학습>

 1. 실무에서의 트리 중위순회 활용

- DB인덱스 구조 (B-Tree, AVL 트리)

 

 2. 추가 연습문제

-

# 1.연습문제 1: 이진 트리의 노드 값 합계
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:

    def sumOfNodes(self, root: Optional[TreeNode]) -> int:
        # 틀린방법
        # answer = 0
        # def sum_node(root, answer):
        #     if root:
        #         sum_node(root.left, answer)
        #         answer += root.val
        #         sum_node(root.right, answer)
        #     return answer
        #
        # return sum_node(root, answer)

        if not root:
            return 0

        # 각 val 을 추가해서 넣어줌
        return root.val + self.sumOfNodes(root.left) + self.sumOfNodes(root.right)



if __name__ == "__main__":
    root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
    sol = Solution()
    print(sol.sumOfNodes(root))  # Expected Output: 15

#연습문제 2: 이진 트리의 최대 깊이
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        # 1 더해주면서 깊이에 대한 누적을 만들어냄
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

if __name__ == "__main__":
    root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
    sol = Solution()
    print(sol.maxDepth(root))  # Expected Output: 3