LeetCode之Construct Binary Search

问题：

方法：
先创建root节点，然后遍历Int数组，因为是先序遍历所以后面的必是叶子节点，所以以root为入口递归插入，如果大于root就递归右子树，如果小于root就递归左子树，如果左节点为null则直接插入，如果右节点为null也直接插入，最后输出root即可。

具体实现：

class ConstructBinarySearchTreeFromPreorderTraversal {
    class TreeNode(var `val`: Int) {
        var left: TreeNode? = null
        var right: TreeNode? = null
    }

    fun bstFromPreorder(preorder: IntArray): TreeNode? {
        if (preorder.isEmpty()) {
            return null
        } else {
            val root = TreeNode(preorder[0])
            for (value in preorder.sliceArray(1..preorder.lastIndex)) {
                build(root, value)
            }
            return root
        }
    }

    private fun build(root: TreeNode, value: Int) {
        if (value > root.`val`) {
            if (root.right != null) {
                root.right?.let { build(it, value) }
            } else {
                root.right = TreeNode(value)
            }
        } else {
            if (root.left != null) {
                root.left?.let { build(it, value) }
            } else {
                root.left = TreeNode(value)
            }
        }
    }
}

fun main(args: Array<String>) {
    val inputArray = intArrayOf(8, 5, 1, 7, 10, 12)
    val constructBinarySearchTreeFromPreorderTraversal = ConstructBinarySearchTreeFromPreorderTraversal()
    constructBinarySearchTreeFromPreorderTraversal.bstFromPreorder(inputArray)
}

有问题随时沟通

具体代码实现可以参考Github