LeetCode in Kotlin
106. Construct Binary Tree from Inorder and Postorder Traversal
Medium
Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
Example 1:
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
Example 2:
Input: inorder = [-1], postorder = [-1]
Output: [-1]
Constraints:
1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000inorderandpostorderconsist of unique values.- Each value of
postorderalso appears ininorder. inorderis guaranteed to be the inorder traversal of the tree.postorderis guaranteed to be the postorder traversal of the tree.
Solution
import com_github_leetcode.TreeNode
/*
* 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 {
fun buildTree(inorder: IntArray, postorder: IntArray): TreeNode? {
val inIndex = intArrayOf(inorder.size - 1)
val postIndex = intArrayOf(postorder.size - 1)
return helper(inorder, postorder, inIndex, postIndex, Int.MAX_VALUE)
}
private fun helper(`in`: IntArray, post: IntArray, index: IntArray, pIndex: IntArray, target: Int): TreeNode? {
if (index[0] < 0 || `in`[index[0]] == target) {
return null
}
val root = TreeNode(post[pIndex[0]--])
root.right = helper(`in`, post, index, pIndex, root.`val`)
index[0]--
root.left = helper(`in`, post, index, pIndex, target)
return root
}
}