Daily LeetCode Challenge - 106. Construct Binary Tree from Inorder and Postorder Traversal

Problem From.

https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

오늘 문제는 트리를 inorder (중위순회) 와 postorder(후위순회) 한 리스트가 주어졌을때, 원래의 tree 를 구하는 문제였다.

이 문제는 DFS 와 순회 규칙을 활용하여 풀 수 있었는데, 먼저 root 노드는 항상 postorder 의 마지막 원소이다. 그리고 그 root 노드를 준으로 inorder 에서 왼쪽으로는 left 에 있는 node 들이 존재하고 오른쪽에는 right 에 있는 node 들이 존재한다.
이 규칙을 DFS 로 반복해나가면 원래의 tree 를 구할 수 있었다.

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    
    var index = 0
    
    fun buildTree(inorder: IntArray, postorder: IntArray): TreeNode? {
        val total = inorder.size
        val map = HashMap<Int,Int>()
        for(i in inorder.indices){
            map[inorder[i]] = i
        }
        return dfs(0, total - 1, map, postorder)
    }
    
    fun dfs(left: Int, right: Int, map: HashMap<Int,Int>, postorder: IntArray) : TreeNode? {
        
        if(left > right) return null
        
        val current = postorder[postorder.size - 1 - index++]
        val root = TreeNode(current)
        root.right = dfs(map.get(current)!!+1, right, map, postorder)
        root.left = dfs(left, map.get(current)!!-1, map, postorder)
        
        return root
    }
}