题解 | #重建二叉树#

/**
 * 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
    }
}