트리

 

 

 

https://takeuforward.org/data-structure/preorder-inorder-postorder-traversals-in-one-traversal/

 

 

https://medium.com/@Roshan-jha/a-comprehensive-guide-to-binary-tree-traversal-in-java-74c86ee23725

 

 

 

 

이진 트리 

 

1. maximum-depth-of-binary-tree

문제 : https://leetcode.com/problems/maximum-depth-of-binary-tree/

 

트리의 깊이를 찾는 문제다. 

먼저 DFS 방식으로 풀 수 있다. 

n : 노드의 갯수, h : 트리의 최대 깊이 

시간 복잡도 : O(n) -> 모든 노드를 한번씩 방문 

공강 복잡도 : O(h) -> 재귀 콜 스택에 최대 h개의 노드 

    fun maxDepth(root: TreeNode?): Int {
        if(root == null) return 0
        var left = maxDepth(root.left)
        var right = maxDepth(root.right)
        return maxOf(left, right) +1
    }

 

 

BFS 방식으로도 풀 수 있다. 

n : 노드의 갯수, w: 최대 넓이 

시간 복잡도 : O(n) -> 모든 노드를 한번씩 방문 

공강 복잡도 : O(w) -> 최악의 경우 큐에 가장 넓은 레벨의 모든 노드가 들어감 

    fun maxDepth(root: TreeNode?): Int {
        if(root == null) return 0
        val queue: Queue<TreeNode> = LinkedList() 
        queue.offer(root)
        var depth = 0
        while(queue.isNotEmpty()) {
            val size = queue.size
            depth ++
            repeat(size) {
                val node = queue.poll()
                node.left?.let{queue.offer(it)}
                node.right?.let{queue.offer(it)}
            }
        }
        return depth
    }

 

 

 

참고 ) 

1. 완전 이진 트리 (balanced)

• 노드 수 n = 2^h - 1 → 균형 잡힘
• DFS 공간: O(log n)
• BFS 공간: O(n/2) (마지막 레벨이 큐에 들어감)

• 시간은 둘 다 O(n)
• 공간은 트리 구조에 따라 DFS가 더 유리하거나 불리할 수 있음
• 균형 트리라면 DFS는 더 메모리 효율적
• BFS는 모든 레벨을 동시에 보기에 **레벨 기반 문제(예: 최소 깊이)**에 더 적합

 

2. same-tree

문제 : https://leetcode.com/problems/same-tree/

두개의 트리가 같은지 물어보는 문제다.

 

DFS 방법 

fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
    if(p == null && q == null) {
        return true 
    }
    if(p == null || q== null ) {
        return false 
    }

    if(p.`val` != q.`val`) {
        return false 
    }
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)

}

 

BFS 방법 

    fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
        if(p == null && q == null) {
            return true 
        }
        if(p == null || q== null ) {
            return false 
        }

        val pQueue:Queue<TreeNode> = LinkedList()
        val qQueue:Queue<TreeNode> = LinkedList() 
        pQueue.offer(p)
        qQueue.offer(q)
        while(pQueue.isNotEmpty() && qQueue.isNotEmpty()) {
            val pTemp = pQueue.poll()
            val qTemp = qQueue.poll()
            if(pTemp == null && qTemp == null) continue
            if(pTemp == null || qTemp == null) return false 
            if(pTemp.`val` != qTemp.`val`) return false 
            pQueue.offer(pTemp.left)
            pQueue.offer(pTemp.right)
            qQueue.offer(qTemp.left)
            qQueue.offer(qTemp.right)
        }

        return pQueue.isEmpty() && qQueue.isEmpty()
    }

 

 

 

 

3. 트리 뒤집기 

문제 : https://leetcode.com/problems/invert-binary-tree/

 

주어진 트리의 좌우를 바꾸는 문제이다. 

 

DFS 

    fun invertTree(root: TreeNode?): TreeNode? {
        if(root == null) {
            return null 
        }

        val left = invertTree(root.left)
        val right = invertTree(root.right)
        root.right = left 
        root.left = right 
        return root 
    }

 

BFS 

fun invertTree(root: TreeNode?): TreeNode? {
        if(root == null) return null 
        val queue: Queue<TreeNode> = LinkedList()
        queue.offer(root)
        while(queue.isNotEmpty()) {
            val node = queue.poll()
            val temp = node.left 
            node.left = node.right 
            node.right = temp 

            node.left?.let{queue.offer(it)}
            node.right?.let{queue.offer(it)}
        }
        return root 
    }

 

 

 

4. 트리의 최대합 구하기 

문제 : https://leetcode.com/problems/binary-tree-maximum-path-sum/submissions/1633699245/

 

 

현재 노드까지의 최대 합을 구하고 갱신해서 최댓값을 구하는 방식으로 DFS로 문제를 풀수 있다. 

BFS방식은 모든 노드를 방문해서 레벨 순서로 순회하고, 현재 노드와 자식들을 보고 지나가기 때문에, 노드 기준으로 양쪽 자식을 더해서 구성하는 판단이 불가능하다. 

✅ BFS로 가능한 범위

문제 종류	DFS 적합	BFS 가능
최대 깊이 (maxDepth)	✅	✅
최소 깊이 (minDepth)	✅	✅
루트→리프 경로합 (hasPathSum)	✅	✅
🔥 임의의 경로에서 최대 합 (maxPathSum)	✅	❌

 

 

class Solution {

    var maxSum = Int.MIN_VALUE
    fun maxPathSum(root: TreeNode?): Int {
        dfs(root)
        return maxSum 
    }

    fun dfs(root: TreeNode?): Int {
        if(root == null) {
            return 0
        }
        val left = maxOf(0, dfs(root.left))
        val right = maxOf(0, dfs(root.right))
        val temp = root.`val` + right + left
        maxSum = maxOf(maxSum, temp)
        return root.`val` + maxOf(right, left)
    }

}

 

 

5. Binary Tree Level Order Traversal 

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

이진 트리의 레벨 별 리스트를 구하는 문제이다.

BFS 방식을 이용하면 직관적으로 풀 수 있다. 

 

BFS를 이용한 방식으로 문제를 풀었다. 

class Solution {
    fun levelOrder(root: TreeNode?): List<List<Int>> {
        if (root == null) {
            return emptyList()
        }
        val answer = mutableListOf<MutableList<Int>>()
        val queue: Queue<Pair<TreeNode, Int>> = LinkedList()
        queue.offer(Pair(root, 0))
        while(queue.isNotEmpty()) {
            val (node, level) = queue.poll()
            if(level == answer.size) {
                answer.add(mutableListOf())
            }
            answer[level].add(node.`val`)
            node.left?.let{queue.offer(Pair(it, level + 1))}
            node.right?.let{queue.offer(Pair(it, level + 1))}
            
        }
        return answer 
    }
}

 

 

DFS 방식을 사용하면 더 간단하게 풀 수 있다. 

DFS로는 다음과 같이 풀 수 있다. 

fun levelOrder(root: TreeNode?): List<List<Int>> {
        val result = mutableListOf<MutableList<Int>>()
        dfs(root, 0, result)
        return result 
    }

    fun dfs(root:TreeNode?, level:Int, result: MutableList<MutableList<Int>>) {
        if(root == null) return 
        if(result.size == level) {
            result.add(mutableListOf())
        }
        result[level].add(root.`val`)
        dfs(root.left, level+1, result)
        dfs(root.right, level+1, result)
    }

 

 

 

6. Serialize and Deserialize Binary Tree 

트리를 인코딩하고 디코딩 하는 문제이다. 

BFS를 사용하면 다음과 같다. 

class Codec() {
	// Encodes a URL to a shortened URL.
    fun serialize(root: TreeNode?): String {
        if(root == null) return "null"
        val queue :Queue<TreeNode> = LinkedList()
        val result = mutableListOf<String>()
        queue.offer(root)
        while(queue.isNotEmpty()) {
            val node = queue.poll()
            if(node == null ) {
                result.add("null")
            }else {
                result.add(node.`val`.toString())
                queue.offer(node.left)
                queue.offer(node.right)
            }
        }
        return result.joinToString(",")
    }

    // Decodes your encoded data to tree.
    fun deserialize(data: String): TreeNode? {
        if(data == "null") return null         
        val values = data.split(",")
        val root = TreeNode(values[0].toInt())
        val queue: Queue<TreeNode> = LinkedList()
        queue.offer(root)
        var i = 1 
        while (queue.isNotEmpty() && i < values.size) {
            val current = queue.poll()
            if(values[i] != "null") {
                val left = TreeNode(values[i].toInt())
                current.left = left 
                queue.offer(left)
            }
            i ++ 
            if(i<values.size && values[i] != "null") {
                val right = TreeNode(values[i].toInt())
                current.right = right 
                queue.offer(right)
            }
            i++
        }
        return root 
    }
}

 

DFS로 풀면 다음과 같다. 

    fun serialize(root:TreeNode?): String {
        val sb = StringBuilder()
        fun dfs(node: TreeNode?) {
            if (node == null) {
                sb.append("null,")
                return 
            }
            sb.append("${node.`val`},")
            dfs(node.left)
            dfs(node.right)
        }
        dfs(root)
        return sb.toString()
    }

    fun deserialize(data: String): TreeNode? {
        val nodes = LinkedList(data.split(",").toList())

        fun dfs(): TreeNode? {
            val value = nodes.poll()
            if(value == "null") return null 
            val node = TreeNode(value.toInt())
            node.left = dfs()
            node.right = dfs()
            return node 
        }
        return dfs()
    }

 

7. Kth Smallest Element 

문제 : https://leetcode.com/problems/kth-smallest-element-in-a-bst/

 

BST에서 k번째로 작은 수를 찾는 문제이다. 

 

처음에는 BST라고 생각을 안하고 넓이 우선 탐색으로 전체 탐색하고 정렬해서 문제를 풀었다. 

    fun kthSmallest(root: TreeNode?, k: Int): Int {
        // 모든 트리를 순회하면서 정렬하기 
        if(root == null || k == 0) return 0
        val answer = mutableListOf<Int>()
        val queue: Queue<TreeNode> = LinkedList()
        queue.offer(root)
        while(queue.isNotEmpty()) {
            val node = queue.poll() 
            answer.add(node.`val`)
            node.left?.let{queue.offer(it)}
            node.right?.let{queue.offer(it)}
        }
        answer.sort()
        return answer[k-1]
    }

 

 

하지만 해당 문제는 이렇게 풀면 안된다. 

 

문제에서 BST로 주어졌는데, 이진 트리 탐색의 경우 다음과 같은 특징을 가진다. 

중위 순회의 경우 순차 정렬된다. (Inorder Traversal을 수행하여 모든 키를 정렬된 순서) 

참고 :https://yoongrammer.tistory.com/71 

[자료구조] 이진 탐색 트리 (BST, Binary Search Tree)

이를 이용해서 문제를 다시푼다. 

H = 트리높이라고할때, 

시간 복잡도 (H + K)이다. 

최악의 경우 (불균형트리) -> O(N), 

균형잡힌 트리인경우 -> O(logN + K) 

    private var count = 0 
    private var result = 0 

    fun kthSmallest(root: TreeNode?, k: Int): Int {
        if(root == null || k == 0) return 0
        inorder(root, k)
        return result
    }

    private fun inorder(node: TreeNode?, k: Int) {
        if(node == null) {
            return 
        }
        inorder(node.left, k)
        count ++ 
        if (count == k) {
            result = node.`val`
            return 
        }
        inorder(node.right, k)
    }

 

 

 

8. Lowest common ancestor of BST 

문제 : https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

 

두개의 노드가 주어지면 공통 부모 노드중에서 가장 최소 부모를 찾는 문제이다. 

BST에서는 해당 노드보다 작으면 왼쪽, 크면 오른쪽에 위치하게 된다는 점을 활용해야한다.

왼쪽 노드 < 현재 노드 < 오른쪽 노드 

즉, 노드가 p, q의 공통 조상이 되려면 다음중 하나여야 한다.

 

• p와 q가 양쪽 자식에 하나씩 있음 (즉, p < node < q 또는 q < node < p)
• p 또는 q가 node 자신임 (자기 자신도 조상이 될 수 있음)

시간복잡도 O(h) 

공간복잡도 O(n) 

- 재귀 호출 스택 사용 

으로 문제를 풀 수 있다. 

class Solution {
    fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
        val value = root?.`val` ?: return null 
        val pVal = p?.`val` ?: return null 
        val qVal = q?.`val` ?: return null 

        return when {
            pVal < value && qVal < value -> lowestCommonAncestor(root.left, p, q)
            pVal >value && qVal > value -> lowestCommonAncestor(root.right, p, q)
            else -> root 
        }

        
    }

}

 

 

 

 

 

반복문으로도 해당 문제를 풀 수 있다. 

명시적 재귀 호출이 없고 node 하나만의 참조만으로 루프를 돌아서 스택도 안 쓰고, 함수 호출도 한 번이므로 공간은 상수이다.

반복문의 경우 공간 복잡도가 O(1)로 줄어든다 .

 

    fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
        var node = root 
        if(q == null || p == null){
            return null 
        }
        while (node != null) {
            val value = node.`val`
            when {
                p.`val`<value && q.`val`< value -> node = node.left 
                p.`val`>value && q.`val`> value -> node = node.right 
                else -> return node 
            }
        }            
        return null 
    }