[파이썬 알고리즘] 14장 - BST 합 (traversal 개념)

https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

Binary Search Tree to Greater Sum Tree - LeetCode

 

<문제>

BST의 각 노드를 현재값보다 더 큰 값을 가진 노드의 합으로 만들어라.

 

<예시>

 

# 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:
    cum_sum = 0
    def bstToGst(self, root: TreeNode) -> TreeNode:
        if root:
            # in-order traversal
            self.bstToGst(root.right)
            self.cum_sum += root.val
            # print(root.val, ":", self.cum_sum)
            root.val = self.cum_sum
            self.bstToGst(root.left)
        return root

 

in-order traversal을 이용하는 문제였다.

 

---

tree traversal은 트리에서 각 노드를 정확히 한 번만 방문하는 과정을 말한다.

더 간한하게는 tree에서 DFS하는 것을 traversal이라고 한다.

그 종류로는 pre-order traversal, in-order traversal, post-order traversal가 있다.

 

1) pre-order traversal

• 1. 노드를 방문한다.
• 2. 왼쪽 subtree에 대해 pre-order traversal
• 3. 오른쪽 subtree에 대해 pre-order traversal

* 여기서 왼쪽을 먼저 traversal하든 오른쪽을 먼저 traversal하든 상관없다.

단지, 노드를 먼저 방문하고 왼쪽/오른쪽 혹은 오른쪽/왼쪽 traversal해야한다.

 

 

2) in-order traversal

• 1. 왼쪽 subtree에 대해 pre-order traversal
• 2. 노드를 방문한다.
• 3. 오른쪽 subtree에 대해 pre-order traversal

3) post-order traversal

• 1. 왼쪽 subtree에 대해 pre-order traversal
• 2. 오른쪽 subtree에 대해 pre-order traversal
• 3. 노드를 방문한다.

 

 

traversal 사용 예시

 

Each mathematical expression can be given as a tree. Of course there are algorithms, but let's start with the manual creation of such a tree from infix notation.
Consider the term "(3+5)*2+(6-3)" - the corresponding syntax tree comes here:

 

위와 같은 수학식을 아래와 같은 tree로 만드는 것을 "parsing"이라고 한다.

이렇게 만들어진 tree에 대해 traversal를 수행하면 연산이 수행되는 것이다.

(이러한 parsing 과정을 컴파일러에서 수행된다)

출처 : http://www.sunshine2k.de/coding/java/SimpleParser/SimpleParser.html

 

+) parsing에 대한 추가 설명

파싱은 어떤 페이지(문서, html 등)에서 내가 원하는 데이터를 특정 패턴이나 순서로 추출해 가공하는 것을 말한다. 먼저 파서는 컴파일의 일부로서 원시 프로그램의 명령문이나 온라인 명령문, HTML 문서 등에서 MArkup Tag 등을 입력으로 받아들여서 구문을 해석할 수 있는 단위와 여러 부분으로 분할해주는 역할을 한다. 이러한 파서(parser) 역할을 하는 컴퓨터가 구문 트리(parse tree)로 재구성하는 구문 분석 과정을 뜻한다. 파싱 과정에서는 부호에 불과한 일련의 문자열이 기계어로 번역되고 의미있는 단위가 된다. 그 종류는 상향식 파싱(bottom-up parsing)과 하향식 파싱(top-down parsing)이 있으며 기계번역, 자연언어처리, 전산언어학 등의 분야에서 주로 사용된다.

 

+) parsing 추가자료

www.sunshine2k.de/coding/java/SimpleParser/SimpleParser.html

Parsing Algorithms