题解 | #重建二叉树#

重建二叉树

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


全部评论

相关推荐

06-20 21:22
已编辑
门头沟学院 Java
纯真的河老师在喝茶:答应了就跑啊,实习随便跑啊,别被pua了,md就是找个廉价劳动力,还平稳过度正式工,到时候跟你说没转正
点赞 评论 收藏
分享
头顶尖尖的程序员:我也是面了三四次才放平心态的。准备好自我介绍,不一定要背熟,可以记事本写下来读。全程控制语速,所有问题都先思考几秒,不要急着答,不要打断面试官说话。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务