| 22 | } |
| 23 | |
| 24 | fun buildSubtree( |
| 25 | left: Int, |
| 26 | right: Int, |
| 27 | preorder: List<Int>, |
| 28 | inorder: List<Int>, |
| 29 | preorderIndex: IntArray, |
| 30 | inorderIndexesMap: Map<Int, Int> |
| 31 | ): TreeNode? { |
| 32 | // Base case: if no elements are in this range, return null. |
| 33 | if (left > right) { |
| 34 | return null |
| 35 | } |
| 36 | val value = preorder[preorderIndex[0]] |
| 37 | // Set 'inorderIndex' to the index of the same value pointed at by |
| 38 | // 'preorderIndex'. |
| 39 | val inorderIndex = inorderIndexesMap[value]!! |
| 40 | val node = TreeNode(value) |
| 41 | // Advance 'preorderIndex' so it points to the value of the next |
| 42 | // node to be created. |
| 43 | preorderIndex[0]++ |
| 44 | // Build the left and right subtrees and connect them to the current |
| 45 | // node. |
| 46 | node.left = |
| 47 | buildSubtree( |
| 48 | left, |
| 49 | inorderIndex - 1, |
| 50 | preorder, |
| 51 | inorder, |
| 52 | preorderIndex + 1, |
| 53 | inorderIndexesMap |
| 54 | ) |
| 55 | node.right = |
| 56 | buildSubtree( |
| 57 | inorderIndex + 1, |
| 58 | right, |
| 59 | preorder, |
| 60 | inorder, |
| 61 | preorderIndex + inorderIndex - left + 1, |
| 62 | inorderIndexesMap |
| 63 | ) |
| 64 | return node |
| 65 | } |