题解 | #重建二叉树#
重建二叉树
https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
kotlin
/**
* class TreeNode(var `val`: Int) {
* var left: TreeNode? = null
* var right: TreeNode? = null
* }
*/
object Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param pre int整型一维数组
* @param vin int整型一维数组
* @return TreeNode类
*/
var pos = 0
fun reConstructBinaryTree(pre: IntArray,vin: IntArray): TreeNode? {
if(pre.size == 0) return null
//类似二分法求解，因为一个数组前序遍历，然后另外一个中序遍历，前序的第一个元素即为根元素值，
//对应于中序数组的下标就可以将中序数组的值分为左右两部分，即根下标的左边为左子树的所有值，右边为右子树的所有值，以此类推来递归
return dfs(pre, vin, 0, pre.size - 1)
}
private fun dfs(pre: IntArray,vin: IntArray, left: Int, right: Int): TreeNode? {
if(left > right || pos == pre.size) return null
val index = vin.indexOf(pre[pos])
val root = TreeNode(pre[pos])
pos++
val leftNode = dfs(pre, vin, left, index - 1)
val rightNode = dfs(pre, vin, index + 1, right)
root.left = leftNode
root.right = rightNode
return root
}
}
